Many-one reduction

A computable function transforms each instance of one decision problem into an instance of another, preserving yes-or-no answers. It shows that solving the target problem would also solve the source problem.

Computable function: A function whose values can be calculated by an algorithm that halts on every input. The transforming map must be computable for the reduction to be effective.
NP-hardness: A property of problems to which every problem in NP reduces in polynomial time. A reduction from an NP-hard problem transfers its difficulty to the target.
Log-space reduction: A many-one reduction computable using logarithmic workspace in the input length. It restricts working memory more sharply than polynomial-time reductions do.
Turing machine: An abstract model of computation that manipulates symbols on a tape according to explicit rules. Computability of the transforming function is commonly defined using this model.
Decision problem: A problem whose answer for each input is yes or no. Many-one reductions compare decision problems by mapping their inputs.
NP-completeness: The property of being both in NP and NP-hard. Many-one reductions are the standard tool for proving NP-hardness and completeness.
Truth-table reduction: A reduction that makes nonadaptive queries to an oracle and computes its answer from their results. It permits multiple queries, but fixes them before any answers are received.
Language (formal languages): A set of finite strings over a fixed alphabet. Decision problems can be represented as languages whose members are yes-instances.
Preimage: The set of inputs that a function maps into a specified set of outputs. The source’s yes-instances must be exactly the preimage of the target’s yes-instances.
Cook–Levin theorem: The theorem that Boolean satisfiability is NP-complete. Its reduction from nondeterministic computation launched the chain of NP-completeness proofs.

Linked from 15 pages