Proving NP-Completeness

The Cook–Levin theorem did the hard, once-in-a-lifetime work: it built a first NP-complete problem, SAT, from scratch. From here on, proving a new problem NP-complete is a craft with a fixed, repeatable recipe — and it never again requires reasoning about all of \mathsf{NP} directly. You stand on the shoulders of a known-hard problem and translate.

That leverage is why the catalogue of NP-complete problems exploded from one to thousands within a few years. Learn the recipe once and you hold a master key: given a new problem, you can usually tell within an afternoon whether it belongs to the intractable club.

The four-step recipe

To prove a target problem B is NP-complete, you do two things — show it is in \mathsf{NP}, and show it is NP-hard — and the second is a single reduction, not a quantifier over the whole class.

1. Membership. Show B \in \mathsf{NP}: describe a short certificate and a polynomial-time verifier. (Skip this and you have only proved NP-hardness.)
2. Pick a known NP-complete problem A that "feels close" to B — 3-SAT for logical structure, a graph problem for a graph target, and so on.
3. Give a polynomial-time reduction A \le_p B: a map f turning any instance x of A into an instance f(x) of B, computable in polynomial time.
4. Prove correctness BOTH ways: x is a yes-instance of A \iff f(x) is a yes-instance of B. Both directions — forgetting one is the classic error.

The direction of the reduction trips everyone up at first: you map the known-hard problem A into your new problem B. You are saying "if B were easy, then A would be easy — but A is known hard, so B must be hard too." Reduce from hard, to new.

Warm-up: SAT to 3-SAT

3-SAT is SAT restricted to clauses of exactly three literals. It is a favourite starting point precisely because it is so rigidly uniform. That it is still NP-complete comes from a clause-splitting reduction from general SAT: a long clause (\ell_1 \vee \ell_2 \vee \cdots \vee \ell_k) is rewritten with fresh "chaining" variables y_i into a conjunction of 3-literal clauses,

(\ell_1 \vee \ell_2 \vee y_1)\;\wedge\;(\bar{y}_1 \vee \ell_3 \vee y_2)\;\wedge\;\cdots\;\wedge\;(\bar{y}_{k-3} \vee \ell_{k-1} \vee \ell_k),

which is satisfiable exactly when the original clause is. Short clauses are padded with duplicate literals. The blow-up is linear, and the new formula uses only 3-clauses — so \text{SAT} \le_p \text{3-SAT}, and 3-SAT inherits NP-hardness. From now on we reduce from 3-SAT, the workhorse of the whole subject.

The star reduction: 3-SAT to Independent Set

An independent set in a graph is a set of vertices with no edge between any two of them. Independent Set asks: is there one of size k? We reduce 3-SAT to it with a beautiful little gadget construction. Given a 3-SAT formula with m clauses:

Clause gadget: for each clause, make a triangle — three vertices, one per literal, all joined. A triangle lets an independent set pick at most one vertex from it.
Consistency edges: join x_i to \bar{x}_i wherever they appear, across triangles. You can never pick a literal and its negation together — that would demand x_i be both true and false.
The ask: set the target size k = m, one vertex per clause.

An independent set of size m must take exactly one literal from each triangle (that's the most a triangle allows, and it needs m in total), and the consistency edges guarantee those choices never contradict each other. Reading the chosen literals as "true" gives a consistent assignment satisfying every clause — and vice versa. The picture below shows the formula (x_1 \vee x_2 \vee x_3) \wedge (\overline{x_1} \vee x_2 \vee \overline{x_3}): two triangles, consistency edges between conflicting literals, and one size-2 independent set highlighted (choosing x_2 from each — the assignment x_2 = \text{true}).

Both directions of correctness fall out of the gadget's geometry, the map is clearly polynomial (3m vertices, a bounded number of edges), and Independent Set is obviously in \mathsf{NP} (the set itself is the certificate). So \text{3-SAT} \le_p \text{Independent Set}, and Independent Set is NP-complete.

One gadget, three theorems: Clique and Vertex Cover for free

The same graph yields two more NP-complete problems almost immediately, through elementary graph dualities — no new gadget needed.

Clique (a set of mutually-adjacent vertices): S is an independent set in G iff S is a clique in the complement graph \overline{G}. So Independent Set of size k in G \iff Clique of size k in \overline{G}.
Vertex Cover (a set touching every edge): S is an independent set iff its complement V \setminus S is a vertex cover. So an independent set of size k exists \iff a vertex cover of size n - k exists.

Each of these is a one-line polynomial-time reduction with a two-way correctness proof — the recipe again, now trivially short. From a single triangle gadget we have harvested four NP-complete problems: 3-SAT, Independent Set, Clique, and Vertex Cover.

Why reductions compose

The whole enterprise works because polynomial-time reductions chain. If A \le_p B and B \le_p C, then A \le_p C: run one polynomial map, then the other, and a polynomial of a polynomial is still a polynomial. So to prove C is NP-hard you only need B \le_p C for any known-NP-hard B — the transitivity back to "all of \mathsf{NP}" is automatic, inherited from Cook–Levin through every link of the chain.

// Reductions compose: A ≤p B and B ≤p C give A ≤p C for free. type Reduction<X, Y> = (x: X) => Y; // polynomial-time instance map function compose<X, Y, Z>( aToB: Reduction<X, Y>, // A ≤p B bToC: Reduction<Y, Z>, // B ≤p C ): Reduction<X, Z> { return (x: X) => bToC(aToB(x)); // still polynomial time overall }

A year after Cook and Levin, Richard Karp published a landmark paper reducing SAT down a branching tree to 21 classic combinatorial problems — clique, vertex cover, Hamiltonian cycle, partition, knapsack and more — each proved NP-complete by exactly this recipe. Because reductions compose, every one of Karp's 21 became a fresh launch-pad for the next proof, and the list snowballed. Today the catalogue runs to thousands across every corner of computing, and the community reflex when meeting a new combinatorial problem is: "which known NP-complete problem does this smell like?" The recipe on this page is the same one used to grow that entire catalogue.

The single most common blunder in an NP-completeness proof is reducing the wrong way. To prove your new problem B is hard, you must map a known-hard problem A into B (A \le_p B) — showing "B is at least as hard as A". Building B \le_p A instead proves the opposite: that B is no harder than A, which says nothing about B's difficulty. And never skip the two-way correctness: an f that is only correct in one direction may turn a no-instance into a yes-instance and silently break the whole argument. Reduce from hard, prove both directions.