Many-One Reductions and What Completeness Requires

An NP-completeness proof has a fixed shape: show the problem is in NP, then exhibit a reduction from a known complete problem. The shape is so standardized that the conditions under which it works are rarely examined. They are worth examining, because the argument depends on properties of the target class as much as on properties of the problem, and the two words in the phrase “NP-complete”, hardness and membership, are doing separate work with separate failure modes.

The reduction relation

A polynomial-time many-one reduction from $L_1$ to $L_2$ is a function $f$ computable in polynomial time such that for every string $x$,

$$x \in L_1 \iff f(x) \in L_2.$$

This is written $L_1 \le_p^m L_2$, and the direction of the arrow is the direction of difficulty: if $L_1$ reduces to $L_2$, then $L_2$ is at least as hard as $L_1$, because an algorithm for $L_2$ combined with $f$ decides $L_1$. The superscript $m$ distinguishes it from other reduction notions; “many-one” means the reduction maps many inputs to one and the decision is made by the target alone, with no ability to call the target repeatedly on different inputs.

The distinction matters. A Turing reduction, which is an algorithm for $L_1$ that may call an oracle for $L_2$ many times, is strictly stronger, and the classes it defines are different. Many-one reductions are the standard in NP-completeness because they are the weakest useful notion: a many-one reduction composes, preserves the structure of the class, and gives the sharpest hardness statements. A problem that is hard under many-one reductions is hard under Turing reductions too, so proving the stronger restriction proves more.

Two properties of $\le_p^m$ are used constantly. It is transitive: if $f$ reduces $L_1$ to $L_2$ and $g$ reduces $L_2$ to $L_3$, then $g \circ f$ reduces $L_1$ to $L_3$, and the composition is polynomial-time computable because a polynomial composed with a polynomial is a polynomial. And it is reflexive via the identity function. So $\le_p^m$ is a preorder, and the equivalence classes it induces are the polynomial-time many-one degrees. Hardness and completeness are statements about where a problem sits in that preorder.

Hardness without membership

A language $L$ is NP-hard if every language in NP reduces to it. A language is NP-complete if it is NP-hard and also in NP. The gap between the two definitions is not a technicality; it is where most of the interesting landscape lives.

The classic example of an NP-hard problem outside NP is the halting problem. Every language in NP reduces to the halting problem, because a decider for halting could be used to decide any NP language by constructing a machine that searches for a certificate and halts when it finds one. But the halting problem is undecidable, hence not in NP. So it is NP-hard and not NP-complete, and the distinction between the two properties is exactly what separates them.

A subtler example comes from the other direction. The problem of deciding whether a boolean formula is a tautology, true under every assignment, is CoNP-complete. It is not known to be in NP, and it is believed not to be, so it is not known to be NP-complete. Whether any CoNP-complete problem is NP-complete is equivalent to whether NP equals CoNP. The asymmetry of the certificate definition is exactly what blocks the obvious reduction.

This is why an NP-completeness proof has two independent halves. The reduction shows hardness. The membership argument shows the problem is not too hard for the class. Omitting the second half leaves a true statement about hardness and a false claim of completeness.

The closure condition

Completeness results exist because NP is closed under polynomial-time reductions in a specific sense: if $L \in \mathrm{NP}$ and $L’ \le_p^m L$, then $L’ \in \mathrm{NP}$. The proof is a composition of machines. Given a polynomial-time verifier for $L$ with certificate relation $R$ and bound $p$, a verifier for $L’$ computes $f(x)$ and then runs the verifier for $L$ on $(f(x), w)$, accepting when that verifier accepts. The certificate for $x$ is the certificate for $f(x)$, and the bound is $p(|f(x)|)$, which is polynomial in $|x|$ because $f$ runs in polynomial time and a polynomial-time machine can only produce polynomially many output symbols.

That last clause is the one that fails for other classes, and its failure is informative. Consider a class defined by a resource bound that a polynomial-time reduction can violate. If the target class is defined by a time bound of $n^{\log n}$, a reduction running in time $n^2$ can blow up the input from length $n$ to length $n^2$, and the target machine’s bound on the larger input is $(n^2)^{\log(n^2)}$, which is far more than the source machine’s bound. Closure fails, and complete problems for such classes are correspondingly harder to come by.

For NP the blow-up is harmless because the bound is a polynomial and polynomials compose. This is the same fact that makes P model-independent, and it is not a coincidence: both properties come from closure of the polynomial functions under composition.

Building a reduction that is actually polynomial

The reduction from 3-SAT to the independent set problem is the cleanest small example, because every step is a local construction and the polynomial bound is visible.

Given a formula in conjunctive normal form with $m$ clauses, each containing exactly three literals over $n$ variables, construct a graph with $3m$ vertices, one per literal occurrence. Connect two vertices with an edge when they are in the same clause, or when they are complementary literals. The claim is that the formula is satisfiable exactly when the graph has an independent set of size $m$.

def sat_to_independent_set(clauses):
    # one vertex per literal occurrence, keyed by (clause index, literal)
    index = {}
    for i, clause in enumerate(clauses):
        for lit in clause:
            index[(i, lit)] = len(index)
    adj = [set() for _ in index]

    # intra-clause edges: at most one vertex per clause can be selected
    for i, clause in enumerate(clauses):
        verts = [index[(i, lit)] for lit in clause]
        for a in range(len(verts)):
            for b in range(a + 1, len(verts)):
                adj[verts[a]].add(verts[b])
                adj[verts[b]].add(verts[a])

    # conflict edges: a literal and its negation cannot both be selected
    by_literal = {}
    for (i, lit), u in index.items():
        by_literal.setdefault(lit, []).append(u)
    for lit, verts in by_literal.items():
        for u in verts:
            for v in by_literal.get(-lit, ()):
                adj[u].add(v)
                adj[v].add(u)
    return adj, len(clauses)

The vertex count is $3m$ and the edge count is at most $3m + 9m^2$, so the graph has polynomial size, and the construction runs in time polynomial in the formula size. Both directions of the equivalence are checked by hand:

If the formula has a satisfying assignment, select from each clause one literal that is true under it. Those $m$ vertices are pairwise non-adjacent: they are in different clauses, so no intra-clause edge connects them, and they are all true under the same assignment, so no two are complementary. This is an independent set of size $m$.

If the graph has an independent set of size $m$, it contains exactly one vertex from each clause, because a set with two vertices from one clause would contain an intra-clause edge. Assign each selected literal true; no conflict arises because the set contains no complementary pair. Every clause has a true literal, so the assignment satisfies the formula.

The construction is a reduction from 3-SAT to independent set, and it is the model for the general pattern: encode each constraint as a local gadget, prove the two directions separately, and count the gadget size to confirm the polynomial bound.

The direction of the arrow in practice

Because reductions compose, a single complete problem bootstraps the rest. Cook proved that satisfiability is NP-complete by a direct argument that encodes the computation of a nondeterministic machine as a formula, the Cook–Levin tableau construction. Karp then reduced satisfiability to twenty-one combinatorial problems, and each of those reductions established completeness for its target. A modern proof usually picks whichever known complete problem makes the gadget smallest.

The practical rule that follows from the direction of the arrow: to show a new problem $X$ is NP-complete, reduce a known NP-complete problem to $X$. Reducing $X$ to a known complete problem shows only that $X$ is in NP, which is the membership half, and the easy half. The confusion is common enough to be worth stating flatly, because the two directions look similar in a diagram and have opposite meanings.

There is a second practical rule about gadget design. The reduction must be parsimonious enough that the target’s solutions correspond to the source’s in both directions. A construction that maps every satisfying assignment to an independent set, but also maps some unsatisfying assignment to one, fails the reverse direction. Gadgets are designed so that the local constraint forces the local choice, and the composition of forced choices is the global correspondence.

Reductions as a measurement

The preorder $\le_p^m$ gives a way to compare problems without knowing whether P equals NP. Two problems in the same degree are equivalent up to polynomial overhead; a problem strictly lower in the preorder is strictly easier, assuming the classes are different. This is a stronger statement than an asymptotic comparison of known algorithms, because it quantifies over all algorithms.

What the preorder cannot do is separate problems inside P. Every language in P reduces to every nontrivial language in P, since a polynomial-time machine can decide the source and then output a fixed member or non-member of the target. So the reductions collapse inside P and carry information only at the boundary. The finer structure inside P requires different tools, and the finer structure above NP requires the polynomial hierarchy, where the quantifier structure rather than the reduction relation does the separating.