NP-Completeness

The previous lesson left us with a claim: inside $\mathsf{NP}$ there are problems that are universally hardest, and they hold the key to the $\mathsf{P}$ versus $\mathsf{NP}$ question. This lesson makes that claim precise. We define what it means to be hardest, identify the first such problem (SAT, via the Cook–Levin theorem), and then show how a single seed problem sprouts an entire forest of equally hard problems through reductions. Finally we distill the whole enterprise into a four-step recipe you can apply to a problem you have never seen before.

NP-hard and NP-complete

Recall that $A{\le }_{P}B$ means $A$ is no harder than $B$. Now imagine a problem $B$ that every problem in $\mathsf{NP}$ is no harder than. Such a $B$ is at least as hard as everything in $\mathsf{NP}$, a ceiling on the whole class.

The distinction matters. $\mathsf{NP}$-hardness is a pure lower bound: $B$ is as hard as anything in $\mathsf{NP}$, but $B$ need not itself be in $\mathsf{NP}$; it could be far harder, even undecidable. $\mathsf{NP}$-complete problems are the ones that are hardest and still belong to $\mathsf{NP}$: they sit exactly at the frontier. They are the hardest problems whose solutions we can still efficiently check.¹

Two consequences make these definitions powerful.

• All $\mathsf{NP}$-complete problems stand or fall together. Suppose $B$ is $\mathsf{NP}$-complete and someone finds a polynomial-time algorithm for $B$. Then for any $A\in \mathsf{NP}$ we have $A{\le }_{P}B$, so $A$ is solvable in polynomial time too, every $A$ at once. Hence $\text{any }\mathsf{NP}\text{-complete problem}\in \mathsf{P}⟹\mathsf{P}=\mathsf{NP}.$ Conversely, proving any single $\mathsf{NP}$-complete problem requires super-polynomial time would prove $\mathsf{P}\ne \mathsf{NP}$. In this sense the thousands of known $\mathsf{NP}$-complete problems are a single problem in many guises.
• Transitivity bootstraps the class. If $C$ is $\mathsf{NP}$-complete and we show $C{\le }_{P}D$ for some $D\in \mathsf{NP}$, then $D$ is $\mathsf{NP}$-complete too: every $A\in \mathsf{NP}$ satisfies $A{\le }_{P}C{\le }_{P}D$, and ${\le }_P$ composes. This is the engine that turns one$\mathsf{NP}$-complete problem into many.

But the engine needs a spark. Transitivity spreads $\mathsf{NP}$-completeness from one problem to the next, yet it presupposes we already have a first $\mathsf{NP}$-complete problem to start from. Where does the first one come from?

The first one: Cook–Levin

The breakthrough, proved independently by Stephen Cook (1971) and Leonid Levin, is that a natural problem is $\mathsf{NP}$-complete from scratch, without reducing from anything, by reasoning directly about computation itself.

The problem is boolean satisfiability, or SAT.

That SAT is in $\mathsf{NP}$ is easy: a satisfying assignment is a certificate, and evaluating $\phi$ on it takes linear time. The deep half is $\mathsf{NP}$-hardness: showing that every $A\in \mathsf{NP}$ reduces to SAT. The idea, which we sketch rather than prove, is to encode computation as logic. Any $A\in \mathsf{NP}$ has a polynomial-time verifier $V$. For an input $x$, the question does some certificate make $V$ accept $x$? is exactly the question is $A$'s answer yes? Cook and Levin build, in polynomial time, a boolean formula ${\phi }_x$ whose variables describe the verifier's entire step-by-step execution, with clauses that force the variables to obey the machine's rules. Then ${\phi }_x$ is satisfiable if and only if some certificate makes $V$ accept, so deciding SAT on ${\phi }_x$ decides $A$ on $x$. Because this works for an arbitrary problem in $\mathsf{NP}$, SAT is $\mathsf{NP}$-hard.²

With one $\mathsf{NP}$-complete problem in hand, the transitivity engine takes over.

The reduction web

Karp's celebrated 1972 paper reduced SAT to twenty-one other problems, showing them all $\mathsf{NP}$-complete and launching the field.³ A convenient waystation is 3-SAT, the special case of SAT in which the formula is in conjunctive normal form with exactly three literals per clause, a big AND of small ORs such as $(x_1\vee \neg x_2\vee x_3)\wedge (\neg x_1\vee x_2\vee x_4)$. One can show $\text{SAT}{\le }_P\text{3-SAT}$, so 3-SAT is itself $\mathsf{NP}$-complete, and its rigid structure makes it the favorite starting point for further reductions.

From 3-SAT the web branches out. A small portion:

Every arrow $X\to Y$ is a reduction $X{\le }_{P}Y$; following arrows back to SAT certifies each box as $\mathsf{NP}$-complete. (The arrows above record one route to each result, not the only one; many of these problems also reduce to each other directly, as we saw with $\text{Independent-Set}$ and Clique last lesson.)

A worked reduction: 3-SAT to Independent-Set

Let us actually build one arrow, the classic $\text{3-SAT}{\le }_P\text{Independent-Set}$. We are given a 3-CNF formula $\phi$ with $m$ clauses and must produce a graph $G$ and integer $k$ such that $G$ has an independent set of size $k$ exactly when $\phi$ is satisfiable.

The construction. For each clause, create a triangle of three vertices, one per literal. So clause $(x_1\vee \neg x_2\vee x_3)$ becomes three mutually-connected vertices labeled $x_1$, $\neg x_2$, $x_3$. Then add a conflict edge between any two vertices in different triangles that hold contradictory literals: one labeled $x_i$ and another labeled $\neg x_i$. Finally set $k=m$, the number of clauses. This is clearly polynomial: $3m$ vertices and at most $O(m^2)$ edges.

Why it works. An independent set may pick at most one vertex from each triangle (the three are mutually adjacent), so an independent set of size $k=m$ must pick exactly one literal from every clause. The conflict edges forbid choosing both $x_i$ and $\neg x_i$ anywhere, so the chosen literals are mutually consistent — they describe a partial truth assignment. Setting each chosen literal true satisfies one literal in every clause, hence satisfies $\phi$. Run the argument backward: a satisfying assignment picks, from each clause, one true literal; those $m$ vertices form an independent set, since two true literals can never be a variable and its negation. Therefore $\phi \text{ is satisfiable}\leftrightarrow G\text{ has an independent set of size }m,$ which is exactly what a valid reduction requires.⁴

Solid edges are the per-clause triangles; dashed edges connect contradictory literals ($x_1$ vs. $\neg x_1$, and $\neg x_2$ vs. $x_2$). Picking one non-conflicting vertex per triangle is exactly a consistent satisfying choice.

The recipe: proving a new problem NP-complete

Once a stockpile of $\mathsf{NP}$-complete problems exists, classifying a new problem $X$ follows a fixed procedure. To prove $X$ is $\mathsf{NP}$-complete, carry out four steps.

1. Show $X\in \mathsf{NP}$. Describe a polynomial-size certificate for yes-instances and argue it can be checked in polynomial time. This is usually the easy step, but skipping it is a real error: an $\mathsf{NP}$-hard problem outside $\mathsf{NP}$ is hard but not complete.
2. Choose a known $\mathsf{NP}$-complete problem $Y$ to reduce from. Pick one whose structure resembles $X$ — 3-SAT for logical or gadget-style constraints, $\text{Vertex-Cover}$ or $\text{Independent-Set}$ for graph selection, $\text{Subset-Sum}$ or $\text{Partition}$ for numeric targets, $\text{Hamiltonian-Cycle}$ for routing.
3. Give a polynomial-time reduction $Y{\le }_{P}X$. Construct, from an arbitrary instance of $Y$, an instance of $X$. This is the creative heart of the proof. Mind the direction: you transform $Y$'s instance into $X$'s, so that solving $X$ would solve $Y$. Reducing the wrong way ($X{\le }_{P}Y$) proves nothing about $X$'s hardness.
4. Prove the reduction correct. Establish the if and only if: a yes-instance of $Y$ maps to a yes-instance of $X$, and conversely every yes-instance of $X$ comes only from a yes-instance of $Y$. Both directions are mandatory; a one-way implication leaves a hole through which false positives or negatives can slip.

Steps 1 and 2 are bookkeeping; steps 3 and 4 are where insight lives.⁵ The worked reduction above is exactly this recipe applied with $Y=\text{3-SAT}$ and $X=\text{Independent-Set}$: the triangles-and-conflicts gadget is step 3, and the two-direction argument is step 4.

Takeaways

• $X$ is $\mathsf{NP}$-hard if every problem in $\mathsf{NP}$ reduces to it (a lower bound); it is $\mathsf{NP}$-complete if it is also in$\mathsf{NP}$, hardest among the efficiently-checkable problems.
• All $\mathsf{NP}$-complete problems share one fate: a polynomial-time algorithm for any of them would prove $\mathsf{P}=\mathsf{NP}$ and solve them all.
• Cook–Levin anchors the theory: SAT is $\mathsf{NP}$-complete, proved directly by encoding any verifier's computation as a boolean formula. From it, 3-SAT and a vast reduction web follow by transitivity.
• The $\text{3-SAT}{\le }_P\text{Independent-Set}$ reduction (a triangle per clause plus conflict edges, with $k=m$) is the model gadget reduction.
• To prove a new problem $\mathsf{NP}$-complete: (1) show membership in $\mathsf{NP}$, (2) pick a known $\mathsf{NP}$-complete $Y$, (3) reduce $Y{\le }_{P}X$ in polynomial time, (4) prove the equivalence both ways, always reducing from the hard problem.