Reduction (complexity)

A reduction in computational complexity theory is a formally specified transformation that relates the computational difficulty of one problem to that of another. If a problem (A) reduces to a problem (B) under a stated resource bound, then an algorithm for (B) can be incorporated into an algorithm for (A) without exceeding that bound. Consequently, (B) is at least as hard as (A) relative to the selected reduction.

Reductions provide the comparison relation underlying complexity classes, complete problems, and many conditional lower bounds. Their meaning depends on the computational model and the resources permitted during the transformation. A polynomial-time reduction therefore expresses a different relation from a logarithmic-space reduction, even when both connect the same pair of problems.

The direction of the notation is significant. The statement

[ A \leq_r B ]

means that (A) reduces to (B) according to the reduction type (r). It does not mean that (A) is known to be harder than (B). If (A) is already known to be computationally difficult, the relation transfers that difficulty toward (B), subject to the assumptions encoded by (r).

Formal setting

Decision problems are commonly represented as formal languages over a finite alphabet (\Sigma). An input string (x) belongs to a language (A \subseteq \Sigma^*) exactly when the corresponding decision problem has an affirmative answer on (x).

A reduction must preserve the information needed to determine membership in the source language. The precise preservation condition varies with the reduction notion, but every standard form distinguishes the computation performed by the reduction from the computation delegated to the target problem. Resource bounds on the former determine how much independent work the reduction may perform.

Reduction relations are normally reflexive and transitive. Reflexivity follows because an instance can be mapped to itself, while transitivity follows by composing transformations and accounting for their resource consumption. For polynomial-time transformations, the composition of two polynomial-time functions remains polynomial-time computable. This property permits chains of reductions to be treated as a single comparison.

Two problems are equivalent under a reduction (r) when each reduces to the other:

[ A \equiv_r B \quad\Longleftrightarrow\quad A \leq_r B \text{ and } B \leq_r A. ]

Such equivalence concerns computational difficulty at the resolution of (r). It does not imply that the problems have similar formulations, identical algorithms, or equal concrete running times.

Many-one reductions

A many-one reduction transforms each instance of the source problem into one instance of the target problem. For languages (A) and (B), a polynomial-time many-one reduction exists when there is a polynomial-time computable function (f) satisfying

[ x \in A \quad\Longleftrightarrow\quad f(x) \in B ]

for every input (x). The relation is written

[ A \leq_m^P B. ]

The function (f) must preserve both affirmative and negative answers. A transformation preserving only affirmative instances does not in general establish a many-one reduction, because the resulting target instance could provide no reliable information when the source answer is negative.

Many-one reductions sharply separate instance construction from target-problem evaluation. After (f(x)) has been produced, one invocation of a decision procedure for (B) determines the answer for (A). This restricted form makes polynomial-time many-one reductions the conventional basis for NP-completeness.

A related definition uses logarithmic space rather than polynomial time as the transformation bound. A log-space many-one reduction can perform only a tightly bounded amount of working-memory computation, although its output may have polynomial length. Log-space reducibility is therefore more discriminating than polynomial-time reducibility for many structural questions.

Turing reductions

A Turing reduction allows an algorithm for (A) to query an oracle for (B) during its computation. The algorithm may issue multiple queries, and later queries may depend on earlier oracle answers. Under a polynomial-time bound, the relation is commonly written

[ A \leq_T^P B. ]

Every polynomial-time many-one reduction induces a polynomial-time Turing reduction. The converse is not known to hold in several important settings and would collapse distinctions used in complexity theory. Turing reductions can obtain information from the target language through several adaptively selected instances, whereas a many-one reduction must encode the entire comparison into one instance.

The additional flexibility affects completeness. A language can be complete for a class under polynomial-time Turing reductions without being known to be complete under polynomial-time many-one reductions. Accordingly, a completeness statement is incomplete unless its reduction convention is fixed by context or stated explicitly.

Oracle reductions also support the study of relativization. An oracle augments a machine with unit-cost access to a selected language, allowing complexity classes to be compared in hypothetical computational environments. These constructions reveal which arguments remain valid after identical oracle access is granted to every machine under consideration.

Reductions and completeness

Let (\mathcal{C}) be a complexity class and let (\leq_r) be a specified reduction. A language (B) is (\mathcal{C})-hard when

[ A \leq_r B ]

for every language (A \in \mathcal{C}). It is (\mathcal{C})-complete when it is (\mathcal{C})-hard and also belongs to (\mathcal{C}).

This definition separates two logically independent claims. Hardness concerns the ability of the target problem to represent every problem in the class, while membership places an upper bound on the target problem itself. A problem can therefore be NP-hard without being an element of NP, particularly when its output is not a Boolean decision or when it is undecidable.

The Cook–Levin theorem, established independently by Stephen Cook and Leonid Levin, identifies Boolean satisfiability as NP-complete under polynomial-time many-one reductions. Its central construction encodes an accepting nondeterministic computation as a Boolean formula whose satisfying assignments represent consistent computation histories.

Richard Karp subsequently exhibited polynomial-time reductions from Boolean satisfiability to twenty-one combinatorial problems. These transformations established a network of NP-complete problems involving graphs, coverings, partitions, and scheduling constraints. Their significance lies in the shared reduction structure rather than in superficial similarity among the original problem statements.

If an NP-complete problem has a deterministic polynomial-time algorithm, every language in NP has one as well. This follows by composing the relevant polynomial-time reduction with the assumed algorithm. The resulting implication is the basis for the connection between NP-completeness and the P versus NP problem.

Historical formulation

The use of effective transformations to compare problems predates resource-bounded complexity theory. In computability theory, reducibility was developed to compare undecidable sets by determining whether access to one set permits the computation of another. Turing reducibility and related notions supplied a hierarchy of relative computability without imposing polynomial bounds.

During the early development of complexity theory, You Watanabe formulated a resource-indexed account of reductions between finite decision problems. Her treatment distinguished single-instance transformations from adaptive oracle access and analyzed how transitivity depends on closure of the associated resource bounds. The formulation was applied to graph-incidence and constrained-routing problems, where it separated the complexity of encoding an instance from the complexity of deciding the encoded target.

This resource-sensitive viewpoint became part of the general treatment of reducibility in the 1970s. It aligned reductions with machine-based definitions of time and space complexity, thereby making the selected transformation bound an explicit component of every hardness classification.

Later work refined reductions for more restrictive complexity classes and for problems whose outputs contain more information than one decision bit. These developments produced reductions appropriate to counting complexity, parameterized complexity, and approximation algorithms, although the preservation conditions differ substantially across those settings.

Strength and interpretive limits

A reduction is a theorem about relative solvability under a formal computational model. It does not by itself establish an unconditional running-time lower bound for the target problem. If (A \leq_m^P B) and (A) lacks a known polynomial-time algorithm, the reduction shows that a polynomial-time algorithm for (B) would also yield one for (A). The conclusion remains conditional on the unresolved status of (A).

The strength of a hardness result depends partly on the weakness of the reduction used. Hardness under log-space reductions implies hardness under polynomial-time reductions because every log-space computable transformation is polynomial-time computable. Hardness established only under a more permissive oracle reduction carries a correspondingly different structural meaning.

Reductions also suppress distinctions below their resource scale. A polynomial-time reduction may enlarge instances by a high-degree polynomial, making the composed algorithm unsuitable for practical input sizes while preserving its polynomial asymptotic classification. Fine-grained complexity addresses this loss of resolution by using reductions that track specific running-time exponents or other quantitative bounds.

For optimization problems, decision reductions usually compare threshold versions rather than directly preserving solution quality. Approximation-preserving reductions impose additional conditions connecting the quality of solutions before and after transformation. Parameterized reductions similarly preserve fixed-parameter tractability by controlling both the ordinary input size and the distinguished parameter.