Module 5 · MIT 18.404J Lectures L14–L16 · Sipser §7.3, §7.4, §7.5
references open in new tabs →💬 Ask Khayyam ↗

NP, NP-completeness & the reduction chain

Finding vs. checking a solution — and one problem that, if easy, makes them all easy.
BCS 402 · Dr. Arash Kermani · CUD
🎧 Narration
🔊 Diagram
Cook–Levin · the verifier's tableau becomes a SAT formula tape position p ──► time t (down) t=0 t=1 t=2 t=3 ⋮ t=k ⋮ p=0p=1p=2p=3p=4p=5p=6p=7p=8 q₀ x₁ x₂ x₃ _ c₁ c₂ c₃ … 2×3 window → SAT clause qₐ ∃ accept somewhere Variables: xt,p,s = "cell (t,p) holds symbol s". Clauses: each 2×3 window must be δ-consistent. Polynomial in |w| ⇒ NP ≤p SAT.
The verifier V running on input x with certificate c sweeps a tape over polynomial time. Each row is a configuration; each 2×3 window must follow δ. Converting each window into a SAT clause produces a formula φx that is satisfiable iff some certificate makes V accept. Every NP problem reduces this way.
🔊 Pipeline
Cook–Levin pipeline · how every NP language becomes a SAT formula Read left to right — each panel makes one of the narrator's abstract terms concrete. ① NP language L "Is x ∈ L?" input x the problem instance cert. c a GUESS — "the witness" L is in NP ⇔ ∃ poly-time TM V such that x ∈ L ⇔ ∃c · V(x, c) accepts. V is the "verifier". run V ② V's tape over time a 2-D grid (the tableau) q₀ x₁ x₂ c₁ c₂ … q_a t=0 t=1 t=2 t=k Row 0 = start config: state, input x, certificate c. Each later row follows by one δ-step. encode ③ Boolean variables one var per (cell, possible symbol) x₁ cell (t=0, p=1) x0,1,a, x0,1,b, … For each (t, p) and each tape symbol s, we make one Boolean variable: xt,p,s = TRUE ⇔ cell (t,p) holds s. ≈ |w|2k · |Γ| variables = polynomial in |w| constrain ④ SAT clauses three families START: row 0 is correct MOVE: every 2×3 window is δ-OK ACCEPT: q_a appears somewhere φx = AND of all 3 polynomial # of clauses over the xt,p,s variables The key equivalence — read the chain right-to-left: φx ∈ SAT ⇔ ∃ truth assignment of all xt,p,s ⇔ ∃ valid tableau for V on (x, c) ⇔ ∃ certificate c s.t. V(x, c) accepts ⇔ x ∈ L. Finding the certificate c = finding a satisfying truth assignment of φx. So solving SAT = solving every NP language — that's why SAT is NP-hard. NP ≤p SAT ⇒ SAT is NP-complete (Cook–Levin).
The same diagram that the narration calls out. ① An NP language is one where every yes-instance has a short, polynomial-time-verifiable certificate c — that's the "guess" the narrator refers to. ② Imagine V running on (x, c): its tape over time is a 2-D grid (the big tableau above). ③ Each (cell, possible tape symbol) pair becomes a separate Boolean variable xt,p,s. ④ Three clause families — START, MOVE (one per 2×3 window), ACCEPT — pin those variables down to exactly the assignments that correspond to valid runs of V. The big SAT formula φx is satisfiable iff there is a certificate c making V accept (x, c), iff x ∈ L. Finding the certificate ≡ finding a satisfying truth assignment. Hence NP ≤p SAT and SAT is NP-complete.
🔊 How to read
How to read this picture

The grid is the verifier's computation tableau. Time flows downward and tape position runs across. Cell (t, p) records what symbol sits on tape position p at time step t — and whether the TM head and state are there. Each row is a complete configuration (tape snapshot + head + state) of the verifier V at one instant.

Row t = 0 (the start configuration). The head is at cell 0 in state q0. Cells 1–3 hold the input x₁ x₂ x₃. Cells 5–7 hold the guessed certificate c₁ c₂ c₃ (the witness we're trying to find).

The dashed orange 2 × 3 window. Any two consecutive rows and three consecutive columns capture one tiny step of the TM. Because the TM's head moves at most one cell per step, what cell (t+1, p) becomes depends only on cells (t, p-1), (t, p), (t, p+1). So if every 2 × 3 window obeys the transition function δ, the whole row-to-row evolution is a legal TM run. Each window becomes a small SAT clause.

The green qa box near t = k. The verifier accepts iff some cell, at some time, holds the accept state qa. That's a single big OR-clause over all (t, p).

The variables. Boolean xt,p,s is true iff cell (t, p) holds symbol s. Total count: nk · nk · |Γ| = polynomial. Three clause families ("start", "every window legal", "accept somewhere") combine into φx. Satisfiable iff some certificate makes V accept ⇒ every NP problem reduces to SAT in polynomial time.

1 · Finding ≪ checking

NP is the class of problems where, given a candidate solution (a certificate), we can verify it in polynomial time. Finding the certificate may be much harder.

🔊 Widget
Verifier vs. solver — race for 3SAT Widget 1 · Auto-plays

Solver: brute force (2ⁿ assignments)

Tested: 0

Verifier: given a witness, check it

Checks: 0
The race
Both panels solve the same instance. The verifier (right) is given the answer and only needs to check it. The solver (left) has to find the answer by searching.
🔊 Definitions
NP definition. A language L ∈ NP iff there is a polynomial-time verifier V such that for every input x, x ∈ L ⇔ ∃c (|c| polynomial in |x|) such that V(x, c) accepts.
Equivalent definition (Sipser Theorem 7.20). NP is also exactly the class of languages decidable by a nondeterministic Turing machine in polynomial time: NP = ⋃k NTIME(nk).

The two definitions are equivalent: given a verifier V and certificate c, a nondeterministic TM can guess c (one symbol per nondeterministic step) and then run V; conversely, an NTM's accepting computation path is itself a polynomial-size certificate. Sipser proves this equivalence in L14 and uses both viewpoints interchangeably.

🔊 Definitions diagram
Two equivalent definitions of NP — and how they translate into each other Left: a deterministic verifier given a witness. Right: a nondeterministic machine that branches. Middle: why they compute the same thing. View 1 · Verifier + Certificate deterministic — given x AND a guess c input x certificate c (a hint we get to use) V poly-time deterministic TM "check if c is a valid witness" accept / reject x ∈ L ⇔ ∃ c such that V(x, c) accepts |c| ≤ polynomial in |x| V runs in time |x|k Why the two views agree each view simulates the other ① Verifier → NTM (left to right) Given V, build N: on input x, ① N nondeterministically GUESSES c, one symbol per nondeterministic step. ② N deterministically runs V(x, c) on the guessed c. ③ N accepts iff V accepts. ② NTM → Verifier (right to left) Given N, build V: V's input is (x, c). Read c as the list of nondeterministic choices. V simulates N(x) along that one path; accepts iff that path accepts. |c| = path length = poly(|x|) — short enough. L ∈ NTIME(nk) ⇔ L has poly verifier View 2 · Nondeterministic TM guesses at every step — a branching tree input x q₀ qₐ ↑ this accepting path IS a certificate c x ∈ L ⇔ N(x) has some accepting path N runs in time |x|k on every path (tree depth = polynomial) Sipser Theorem 7.20: NP = ⋃k NTIME(nk) = { L : L has a polynomial-time verifier }
Two equivalent definitions of NP. Left (verifier view): a deterministic poly-time TM V is given both the input x AND a "certificate" c — a hint at most polynomial in |x|. x ∈ L iff some c convinces V to accept. Right (nondeterministic view): an NTM N starts on input x and at every step nondeterministically branches into a tree of possible computations. x ∈ L iff at least one path in that tree ends in q_accept. Middle (bridge): the two views simulate each other — N can simulate V by first GUESSING c (one symbol per nondeterministic branch) then running V; V can simulate N by reading c as the list of nondeterministic choices along the accepting path. So "the certificate c" and "the sequence of nondeterministic choices on an accepting path" are the same thing in two different notations. Sipser uses both viewpoints interchangeably throughout chapter 7.
🎧 Narration

2 · SAT — the canonical NP problem

SAT: given a Boolean formula, is there an assignment that makes it true? Watch a small instance below; click on a variable to flip it and see clauses turn green/red.

🔊 Widget
Interactive SAT — click to flip variables Widget 2

3-SAT

3-SAT restricts each clause to exactly 3 literals. The class doesn't get easier — 3-SAT is still NP-complete (we'll see why below) — but it is structurally simpler, which makes it the standard launching pad for most reductions.

🎧 Narration

3 · Cook–Levin: every NP problem reduces to SAT

The Cook–Levin theorem says SAT is NP-hard: every problem in NP reduces to SAT in polynomial time. The proof is a tour-de-force of encoding: given an NP language L with verifier V running in time nk, build a SAT formula φx asserting "there exists a computation of V on (x, c) that accepts." The formula is satisfiable iff x ∈ L.

The formula has clauses that say: "the start of the tape is the correct initial configuration", "each cell changes consistent with δ", "an accept state appears somewhere". Putting them together: the computation tableau.

🔊 Widget
The Cook–Levin tableau — building computation as a grid Widget 3 · Auto-plays
What you'll see
A nk × nk grid where row i is the configuration of the verifier at time i. The 2×3 "windows" represent local consistency constraints encoded as SAT clauses.
🎧 Narration

4 · The reduction chain: how NP-completeness spreads

🔊 Diagram
The NP-completeness reduction tree · every node reduces from its parent SAT Cook–Levin (1971) 3-SAT CLIQUE SUBSET-SUM HAM-PATH 3-COLOR PARTITION VERTEX-COVER KNAPSACK TSP Edge A → B means "we know a polynomial-time reduction A → B, so B is at least as hard as A."
The NP-completeness family tree rooted at SAT. Every edge is a known polynomial-time reduction. Karp's 1972 paper added 21 such reductions in one stroke; today the tree has hundreds of nodes.

Once SAT is NP-hard, every problem we reduce from SAT inherits NP-hardness. A chain of polynomial-time reductions:

SAT  ⇒  3SAT  ⇒  CLIQUE  ⇒  VERTEX-COVER  ⇒  HAMPATH  ⇒  SUBSET-SUM
🔊 Widget
Reduction chain — watch one problem morph into another Widget 4 · Auto-plays
🔊 Key idea
Every problem in the chain is NP-complete. If you find a polynomial-time algorithm for any one of them, you've collapsed P = NP, and won a million dollars.
🎧 Narration

5 · The whole map

🔊 Widget
P, NP, and the NP-complete frontier Widget 5
NP verifiable in polynomial time P solvable in polynomial time PATH 2-COL PRIMES SAT 3SAT CLIQUE VERTEX COVER HAMPATH SUBSET SUM NP-complete frontier ↑ Cook–Levin reductions chain ↓ NP-complete problems (orange) sit at the boundary of NP. If any one of them is in P, then all of NP collapses into P.
🎧 Narration

6 · Practice (Sipser §7.3–§7.5)

Sipser 7.18

Show that if P = NP, then every language in P, except ∅ and Σ*, is NP-complete.

Show solution outline
If P = NP, every nontrivial L ∈ P is in NP. For NP-hardness: given any L' ∈ NP = P, build a poly-time reduction to L. Pick any x_0 ∈ L and x_1 ∉ L. The reduction f: on input w, decide if w ∈ L' (in P!); if yes output x_0, else x_1. Then w ∈ L' iff f(w) ∈ L.
Sipser 7.21

Show that PATH is in P, and that HAMPATH is in NP.

Show solution outline
PATH: BFS. HAMPATH verifier: certificate is a sequence of vertices; verify length n, all distinct, consecutive edges in graph, starts at s, ends at t. All polynomial.
Sipser 7.23

Show that NP is closed under union and concatenation.

Show solution outline
Union: V'(x, c) = V_1(x, c) OR V_2(x, c) (with appropriate flag). Concatenation: V'(x, ⟨i, c_1, c_2⟩) accepts iff x = uv with |u|=i, V_1(u, c_1), V_2(v, c_2). All polynomial.
Sipser 7.28

Show that the 3COLOR = {⟨G⟩ : G is 3-colorable} problem is NP-complete.

Show solution outline
In NP: certificate is a coloring; check each edge has different colors at endpoints. NP-hard: reduce from 3SAT. For each variable, gadgets enforcing T/F coloring; for each clause, gadgets that are 3-colorable iff the clause is satisfied. Standard textbook construction.
Sipser 7.32

Show that SUBSET-SUM is NP-complete (in NP and 3SAT ≤_p SUBSET-SUM).

Show solution outline
In NP: certificate is a subset, sum it. NP-hard via 3SAT: for n variables and m clauses, build numbers encoding variable assignments and clause satisfaction in different digit positions; target sum forces each variable to be picked exactly one way and each clause to be satisfied.
Sipser 7.34

Show that if P = NP, you can find a satisfying assignment for any satisfiable 3CNF formula in polynomial time (search-to-decision reduction).

Show solution outline
Self-reducibility: given φ, set x_1 = T; check if φ|x_1=T is satisfiable (use the assumed P-time SAT decider); if so, recurse, else set x_1 = F and recurse. n applications of the decider; polynomial total.
🎧 Narration

One-sentence summary

🔊 Summary
NP is the class of decision problems whose "yes" instances admit polynomial-time-verifiable certificates; SAT is NP-complete (Cook–Levin) and from SAT a chain of polynomial-time reductions establishes NP-completeness for hundreds of natural problems.

Next → Module 6: Space, PSPACE & Games