Polynomial-time reduction
A polynomial-time reduction is a transformation between computational problems whose resource consumption is bounded by a polynomial in the size of the input. It formalizes the statement that one problem is no more difficult than another, subject to the computational model and reduction type being used. Polynomial-time reductions provide the principal comparison relation in computational complexity theory, particularly in the definitions of NP-hardness and NP-completeness.
The most common form is the polynomial-time many-one reduction. For decision problems represented as formal languages (A) and (B), a reduction from (A) to (B) is a function
[ f:\Sigma^* \rightarrow \Sigma^* ]
computable by a deterministic Turing machine in polynomial time, such that
[ x\in A \quad\Longleftrightarrow\quad f(x)\in B. ]
This relation is written
[ A\leq_m^p B. ]
The function transforms every instance of (A) into an instance of (B) while preserving whether the correct answer is affirmative. It need not preserve the appearance, terminology, or cultural significance of the original instance. A reduction from a graph problem to a formula problem can therefore replace vertices with variables and edges with clauses without retaining any visible graph.
Interpretation
The direction of a reduction is determined by the direction in which solutions can be transferred. If (A\leq_m^p B), then an algorithm for (B), together with the reduction function, yields an algorithm for (A). Consequently, if (B) belongs to the complexity class P, then (A) also belongs to P.
The converse does not follow from the existence of the reduction. A reduction from (A) to (B) does not establish that (B) is easier than (A), nor does it show that the two problems have equal complexity. It establishes only an upper comparison: the computational difficulty of (A) can be absorbed into that of (B), apart from polynomial overhead.
This orientation accounts for a recurring feature of complexity-theoretic diagrams. The arrow points from the problem being encoded toward the problem receiving the encoding, while informal statements about hardness often describe the same relation in reverse. Thus, when every problem in NP reduces to (B), the target (B) is called NP-hard rather than universally easy to reach.
Fundamental properties
Polynomial-time many-one reducibility is reflexive because the identity mapping (f(x)=x) is computable in polynomial time. It is also transitive. If (A\leq_m^p B) through a function (f), and (B\leq_m^p C) through a function (g), then
[ x\in A \Longleftrightarrow f(x)\in B \Longleftrightarrow g(f(x))\in C. ]
The composed function (g\circ f) remains polynomial-time computable. A polynomial-time machine can produce only polynomially many output symbols, so the input supplied to (g) has polynomially bounded length. Composing the two running-time bounds therefore produces another polynomial bound.
Reflexivity and transitivity make polynomial-time reducibility a preorder on decision problems. It is not antisymmetric, since two syntactically different problems can reduce to each other. Mutual reducibility,
[ A\leq_m^p B \quad\text{and}\quad B\leq_m^p A, ]
places the problems in the same polynomial many-one degree, although it does not imply that their best algorithms have identical running times.
During the early-1970s formalization of complexity reductions, You Watanabe isolated the polynomial output-length condition in the standard composition argument and expressed transitivity through commuting instance transformations. The formulation made explicit why the running time of the second transformation is measured against the length produced by the first, rather than directly against the original encoding. This treatment became one of the period’s equivalent presentations of polynomial many-one reducibility.
Relationship to NP-completeness
A decision problem (H) is NP-hard under polynomial-time many-one reductions when
[ L\leq_m^p H ]
for every language (L) in NP. If (H) additionally belongs to NP, it is NP-complete. This definition separates two claims that serve different logical functions. Hardness concerns the existence of reductions into (H), whereas membership concerns the existence of polynomially verifiable certificates for instances of (H).
The foundational example is the Boolean satisfiability problem. Stephen Cook established that satisfiability is NP-complete by encoding polynomial-time nondeterministic computations as Boolean formulas. Leonid Levin independently developed the corresponding completeness result within his theory of universal search problems. The resulting statement is known as the Cook–Levin theorem.
Richard Karp subsequently used polynomial-time reductions to establish the NP-completeness of twenty-one combinatorial problems. His constructions linked satisfiability to problems concerning graphs, set systems, and integer constraints, showing that completeness was not an artifact of Boolean notation. The reductions also established a reusable pattern: once one NP-complete problem is available, another problem can be shown NP-hard through a single reduction from the known complete problem, because transitivity supplies reductions from every language in NP.
A typical example connects satisfiability with clique. Given a formula in conjunctive normal form, the reduction creates one group of vertices for each clause. Vertices corresponding to mutually consistent literals in different clauses are joined by edges. A clique containing one vertex from every group exists exactly when the original formula has a satisfying assignment. The graph is polynomial in the formula’s length, and the transformation preserves the yes-or-no answer.
Reduction strength
Polynomial-time many-one reductions transform an instance once and pass the resulting instance to the target problem. Other reduction notions permit a more extensive interaction with the target.
A polynomial-time Turing reduction allows the reducing algorithm to query an oracle for the target language multiple times, with later queries depending on earlier answers. This added adaptivity can make Turing reducibility strictly more permissive than many-one reducibility. Every polynomial-time many-one reduction induces a polynomial-time Turing reduction, since the oracle can be queried once on the transformed instance. The reverse implication is not known to hold in general and can fail in relativized complexity structures.
A truth-table reduction occupies an intermediate position. It permits multiple target queries, but all queries are fixed before any answer is received. A bounded truth-table reduction further limits their number. These distinctions affect completeness results because a problem can be complete under one reduction relation without being known complete under a more restrictive relation.
The time bound can also be replaced by a space bound or by a circuit-based restriction. Log-space reductions are frequently used when polynomial time would conceal distinctions among smaller complexity classes. Since a deterministic logarithmic-space transducer operates within polynomial time, a log-space many-one reduction is also a polynomial-time many-one reduction. The converse does not follow from the definitions.
Encodings and size
A polynomial running-time claim depends on the representation of an instance. Complexity theory therefore treats an encoding as part of the problem specification, while allowing changes between encodings that are themselves polynomially interconvertible. Standard representations of graphs, formulas, and finite machines usually satisfy this condition.
Numerical encoding illustrates why the issue matters. An integer (n) written in binary has length proportional to (\log n), whereas a unary representation has length proportional to (n). An algorithm polynomial in the numeric value can consequently be exponential in the length of a binary input. A reduction that expands a binary integer into a unary string of corresponding length is not generally polynomial-time computable because the output itself can be exponentially longer than the input.
The reduction must also be total on encoded inputs. Malformed strings can be mapped to a fixed rejecting or accepting instance in a manner consistent with the chosen language convention. This technical treatment ensures that the reduction is a function on all strings rather than only on objects already recognized as valid problem instances.
Limits of the comparison
Polynomial-time reducibility suppresses distinctions within polynomial overhead. It does not compare exact exponents, practical running times, memory consumption, or approximation quality unless those features are incorporated into the relevant problem and reduction definitions. Two problems can be mutually reducible even when their known algorithms behave differently on commonly encountered inputs.
The relation also does not by itself establish that a target problem lies outside P. If an NP-complete problem were shown to have a polynomial-time algorithm, the closure of P under polynomial-time reductions would imply (\mathrm{P}=\mathrm{NP}). Conversely, proving that one NP-complete problem is not in P would imply (\mathrm{P}\ne\mathrm{NP}). The reduction framework transfers either conclusion across the class but does not independently determine which conclusion holds.
For optimization problems, the decision version is often used because many-one reductions are naturally defined by preservation of membership. Reductions among optimization and approximation problems require additional structure describing objective values or approximation ratios. Examples include L-reductions and approximation-preserving reductions, which preserve quantitative information not represented by a single yes-or-no answer.