From Reductions to Hardness
A polynomial-time many-one reduction compares two decision problems by translating instances of one into instances of the other. Its direction matters: if problem \(A\) reduces to problem \(B\), then an efficient algorithm for \(B\) would give an efficient algorithm for \(A\). Consequently, a reduction from a problem already known to be hard can transfer that hardness to the problem it reduces to. This tutorial defines NP-hardness and NP-completeness, proves the criterion for recognizing NP-completeness, and shows how to reason correctly about chains of reductions.
We treat a decision problem as a language: a set \(L\) of finite encoded strings, whose members are the yes-instances. The length of an input string \(x\) is written \(|x|\). We use the standard verifier definition of NP: \(L\) is in NP if there is a deterministic polynomial-time algorithm \(V\) and a polynomial bound \(p\) such that \(x\in L\) exactly when some certificate \(z\), with \(|z|\le p(|x|)\), satisfies \(V(x,z)=1\). The certificate is a witness that can be checked efficiently; the definition does not require that a no-instance have a short certificate of its own.
The map \(f\) is a translation of instances: it need not preserve their appearance or size exactly. It must, however, run in polynomial time and preserve the yes/no answer. If an algorithm decides \(B\), then to decide \(A\) one computes \(f(x)\) and runs the \(B\)-algorithm on that output. This explains why \(A\le_p B\) says that \(B\) is at least as hard as \(A\), rather than the other way around.
An NP-hard problem is not required to lie in NP. It may lack a polynomial-time verifier of the specified kind, or may not be a decision problem in the first place in broader uses of the term. NP-completeness adds the membership condition: an NP-complete problem is both at least as hard as every problem in NP and itself verifiable in polynomial time.
The Criterion for NP-Completeness
Proof. Suppose first that \(B\) is NP-complete. By definition, NP-completeness includes both \(B\in\mathrm{NP}\) and NP-hardness. By the definition of NP-hardness, every \(A\in\mathrm{NP}\) satisfies \(A\le_p B\). Conversely, suppose that \(B\in\mathrm{NP}\) and every \(A\in\mathrm{NP}\) satisfies \(A\le_p B\). The second condition is precisely that \(B\) is NP-hard. Combining it with \(B\in\mathrm{NP}\) gives that \(B\) is NP-complete. Both implications follow directly from the definitions. \(\square\)
The theorem is a criterion, not by itself a practical instruction to construct reductions from every language in NP. A useful proof usually starts from one language already known to be NP-complete. It proves a reduction from that source to the new problem and separately proves that the new problem belongs to NP. The next result explains why that one reduction can be enough.
Proof. Let \(f\) witness \(A\le_p B\), and let \(g\) witness \(B\le_p C\). Define \(h(x)=g(f(x))\). For every \(x\), the reduction properties give \(x\in A\) if and only if \(f(x)\in B\), and \(f(x)\in B\) if and only if \(g(f(x))\in C\). Therefore \(x\in A\) if and only if \(h(x)\in C\). It remains to check the running time. Since \(f\) runs in polynomial time, there is a polynomial \(p\) with \(|f(x)|\le p(|x|)\). If \(g\) runs in time bounded by a polynomial \(q\) of its input length, computing \(g(f(x))\) takes at most polynomial time in \(|x|\): its time is bounded by the time for \(f\), plus \(q(p(|x|))\). Thus \(h\) is a polynomial-time reduction. If \(B\) is NP-hard, then for every \(A\in\mathrm{NP}\), \(A\le_p B\); transitivity gives \(A\le_p C\), so \(C\) is NP-hard. If also \(C\in\mathrm{NP}\), the definition makes \(C\) NP-complete. \(\square\)
Worked Example: Checking a Reduction on Every Input Type
Let \(A\) be the language of binary strings whose first bit is \(1\), and let \(B\) be the language of binary strings that contain \(11\) as two consecutive bits. The empty string is not in \(A\). Define \(f\) by outputting \(11\) when the input starts with \(1\), and outputting \(00\) otherwise.
For an arbitrary input \(x\), the map examines its first bit, if one exists, and outputs a string of length \(2\). It therefore runs in time linear in \(|x|\) (and takes constant time on the empty input). If \(x\) starts with \(1\), then \(f(x)=11\), which contains \(11\), so \(f(x)\in B\). If \(x\) does not start with \(1\), including when \(x\) is empty, then \(f(x)=00\), which has no consecutive \(11\), so \(f(x)\notin B\). Thus \(x\in A\) if and only if \(f(x)\in B\).
For instance, \(x=1010\) starts with \(1\), so \(f(1010)=11\in B\). The input \(x=001\) does not start with \(1\), so \(f(001)=00\notin B\). For the empty input, \(f(\varepsilon)=00\notin B\), matching \(\varepsilon\notin A\).
Check: The map satisfies both directions of the membership equivalence, including the empty string. Its output has length \(2\) for every input, and the first-bit test is polynomial-time. Hence \(A\le_p B\). This establishes a reduction only; it does not establish that either language is NP-hard.
Reduction Chains in Practice
For a chain \(A\le_p B\le_p C\), the hardness information flows from left to right: an algorithm for \(C\) would decide \(B\), and through the composed translations it would decide \(A\). If \(A\) is NP-hard, this chain proves that both \(B\) and \(C\) are NP-hard. But if only \(C\) is known to be hard, the chain does not establish hardness of \(B\): a reduction to \(C\) says that \(C\) can solve \(B\)'s instances, not that solving \(B\) would solve \(C\).
Worked Example: Composing Two Explicit Reductions
Continue with the language \(B\) of strings containing \(11\). Let \(C\) be the language of strings containing \(111\) as three consecutive bits. Define \(g(y)=111\) if \(y\) contains \(11\), and \(g(y)=000\) otherwise. The test scans \(y\), so the map takes time linear in \(|y|\).
If \(y\in B\), then \(g(y)=111\in C\). If \(y\notin B\), then \(g(y)=000\notin C\). Therefore \(y\in B\) if and only if \(g(y)\in C\), and \(B\le_p C\).
Now compute the composition on inputs from the first example. For \(x=1010\), the first map gives \(f(x)=11\). This string contains \(11\), so \(g(f(x))=g(11)=111\), which belongs to \(C\). For \(x=001\), \(f(x)=00\), which does not contain \(11\), so \(g(f(x))=g(00)=000\), which does not belong to \(C\). For \(x=\varepsilon\), the same calculation gives \(f(\varepsilon)=00\) and \(g(f(\varepsilon))=000\), a no-instance of \(C\).
In general, \(g(f(x))=111\) exactly when \(f(x)\) contains \(11\), which happens exactly when \(x\) starts with \(1\). Otherwise \(g(f(x))=000\). This verifies directly that the composed map preserves membership for all inputs, not just the three tested strings. The example demonstrates transitivity, but since these particular languages have simple direct tests, it does not prove any of them NP-hard.
Worked Example: A Complete Problem Built from a Known Source
Suppose \(H\) is a language already known to be NP-complete. Define a new language \(Q=\{1x:x\in H\}\), where \(1x\) means the string formed by placing a leading \(1\) before \(x\). We verify the two conditions in the NP-completeness criterion.
First, reduce \(H\) to \(Q\) by \(r(x)=1x\). The map takes time linear in \(|x|\), and \(x\in H\) if and only if \(1x\in Q\), by the definition of \(Q\). Hence \(H\le_p Q\). For any language \(A\in\mathrm{NP}\), the assumption that \(H\) is NP-hard gives \(A\le_p H\). Transitivity then gives \(A\le_p Q\). Thus \(Q\) is NP-hard.
Second, \(Q\in\mathrm{NP}\). On an input string \(y\), a verifier first checks whether \(y\) has a leading \(1\). If it does not, it rejects. If \(y=1x\), it uses the polynomial-time verifier for \(H\) on \(x\) and its certificate. The leading-bit check and the verification for \(H\) together take polynomial time in \(|y|\); certificate lengths remain polynomial because \(|x|=|y|-1\). This accepts exactly the strings in \(Q\). Therefore \(Q\in\mathrm{NP}\), and since it is also NP-hard, \(Q\) is NP-complete.
Check: If \(x\in H\), then \(1x\in Q\) by definition; if \(x\notin H\), then \(1x\notin Q\). The membership proof uses the verifier for \(H\), not an assumption that the reduction alone supplies a certificate. The construction is conditional on \(H\) being known NP-complete, as stated.
Common Mistakes and a Reliable Proof Plan
Reversing the reduction. A frequent error is to show \(B\le_p H\), where \(H\) is known to be NP-hard, and conclude that \(B\) is NP-hard. The implication goes the other way: \(B\le_p H\) shows that \(H\) is at least as hard as \(B\). To transfer hardness to \(B\), the required direction is \(H\le_p B\). In a concrete check, if \(H\) is NP-hard and the only map provided is \(B\to H\), then for an arbitrary \(A\in\mathrm{NP}\) we know \(A\le_p H\), but this does not give a map from \(A\) to \(B\). The needed link is missing.
Proving hardness but forgetting membership. A reduction from an NP-hard source proves that the target is NP-hard, provided the reduction is valid. It does not prove that the target belongs to NP. For NP-completeness, give a separate verifier argument and state why its certificate length and running time are polynomial.
Checking only yes-instances. A valid many-one reduction must preserve nonmembership as well as membership. A construction that maps every yes-instance to a yes-instance but sometimes maps no-instances to yes-instances does not establish the required equivalence. In examples, check both cases explicitly, including boundary inputs such as the empty string when the chosen encoding permits it.
A dependable proof of NP-completeness therefore has two parts:
- Choose a source problem \(H\) that is already known to be NP-complete, and construct a polynomial-time map from \(H\) to the target \(B\).
- Prove for every source instance \(x\) that \(x\in H\) exactly when its image belongs to \(B\), then give a polynomial-time verifier showing \(B\in\mathrm{NP}\).
The first part makes \(B\) NP-hard: every language in NP reduces to \(H\), and the reductions compose. The second part supplies membership in NP. Keeping these obligations separate makes the direction of the reduction and the role of certificates explicit.
Check Your Understanding
For each question, track both the reduction direction and the membership condition.
- If \(A\le_p B\) and \(B\le_p C\), what is the composed reduction, and why does it still run in polynomial time?
- Suppose \(H\) is NP-hard and \(H\le_p Q\). What does this imply about \(Q\)? What extra condition makes \(Q\) NP-complete?
- Suppose \(H\) is NP-hard and \(Q\le_p H\). Does this show that \(Q\) is NP-hard? Explain which direction is missing.
- Why does proving \(H\le_p Q\) not, by itself, show that \(Q\in\mathrm{NP}\)?
- For the map \(f\) in the first worked example, verify the membership equivalence when the input is the empty string.