47.02.02 · theoretical-cs / complexity-fundamentals

NP-Completeness and the Cook-Levin Theorem

shipped3 tiersLean: none

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4-7.5; Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §2.3-2.5 (full tableau construction, circuit-SAT to SAT reduction, Ladner's theorem, structure of NP-complete problems)

Intuition Beginner

Imagine you are given a massive jigsaw puzzle. Checking whether a proposed solution is correct is quick — you just verify that every piece fits. But finding the solution yourself might take a very long time.

This is the essence of NP. A problem is in NP if every "yes" answer comes with a short proof that can be verified quickly. SAT, the Boolean satisfiability problem, is the canonical example: given a formula like "(x or y) and (not x or z)", is there an assignment of true/false values to the variables that makes the whole formula true? Checking a proposed assignment is easy. Finding one could be very hard.

NP-completeness identifies the hardest problems in NP. A problem is NP-complete if (1) it is in NP, and (2) every other problem in NP can be converted into it efficiently (in polynomial time). This means if you could solve any single NP-complete problem quickly, you could solve every NP problem quickly, and P would equal NP.

The Cook-Levin theorem (1971) proves that SAT is NP-complete. The proof works by showing that the computation of any Turing machine (as defined in 42.04.01) solving an NP problem can be encoded as a Boolean formula. The formula is satisfiable if and only if the machine accepts the input. This encoding converts the question "does this machine accept this input?" into "is this formula satisfiable?", establishing SAT as a universal hard problem.

Visual Beginner

The structure of NP-completeness: every problem in NP reduces to SAT.

   NP problems          Polynomial        SAT
  ┌───────────┐        reductions      ┌─────┐
  │  CLIQUE   │ ──────────────────────→ │     │
  │  TSP      │ ──────────────────────→ │     │
  │  3-COLOR  │ ──────────────────────→ │ SAT │
  │  SUBSET-SUM│ ──────────────────────→ │     │
  │  ...      │ ──────────────────────→ │     │
  └───────────┘                         └─────┘

A polynomial-time reduction from problem A to problem B is a function $f$ computable in polynomial time such that $x \in A$ if and only if $f (x) \in B$ .

Problem	In NP?	NP-complete?	Known poly algorithm?
SAT	Yes	Yes (Cook-Levin)	None known
3-SAT	Yes	Yes (reduction from SAT)	None known
Sorting	Yes	No (in P)	Yes
Halting problem	No (undecidable)	No	No

Worked example Beginner

We reduce SAT to 3-SAT to show 3-SAT is NP-complete.

A SAT instance: $(x_{1} \lor x_{2}) \land (\neg x_{1} \lor x_{3} \lor x_{4} \lor \neg x_{2})$ .

The second clause has 4 literals, so this is not a 3-SAT instance. We convert it using auxiliary variables.

Clause splitting. Replace $(\neg x_{1} \lor x_{3} \lor x_{4} \lor \neg x_{2})$ with two 3-literal clauses using a new variable $z$ :

$(\neg x_{1} \lor x_{3} \lor z) \land (\neg z \lor x_{4} \lor \neg x_{2})$

Correctness. If the original 4-literal clause is satisfiable, at least one literal is true. If $\neg x_{1}$ or $x_{3}$ is true, set $z$ to false: both new clauses are satisfied. If $x_{4}$ or $\neg x_{2}$ is true, set $z$ to true: both new clauses are satisfied.

Conversely, if the new clauses are both satisfied, consider $z$ . If $z$ is false, then $\neg x_{1} \lor x_{3}$ must be true. If $z$ is true, then $x_{4} \lor \neg x_{2}$ must be true. Either way, at least one literal in the original clause is true.

This gadget construction splits any clause of length $k > 3$ into clauses of length 3 using $k - 3$ new variables. The formula grows polynomially, and the conversion runs in polynomial time.

Check your understanding Beginner

Formal definition Intermediate+

Definition (NP-completeness). A language $B$ is NP-complete if:

$B \in NP$ , and
For every $A \in NP$ , $A \leq_{p} B$ (every language in NP is polynomial-time reducible to $B$ ).

Condition (2) is equivalent to: there exists an NP-complete language $C$ such that $C \leq_{p} B$ . This is the standard method for proving new problems NP-complete.

Definition (computation tableau). A Turing machine (as defined in 42.04.01) $M$ running on input $x$ of length $n$ within time $t = n^{k}$ produces a tableau — a $t \times t$ table where row $i$ represents the configuration of $M$ at step $i$ . Each cell contains a symbol from the tape alphabet, a state, or a combination (the cell under the tape head carries both the tape symbol and the current state).

Definition (SAT). The Boolean satisfiability problem is:

SAT = {φ : φ is a satisfiable Boolean formula in conjunctive normal form (CNF)} .

A Boolean formula $φ$ in CNF is a conjunction of clauses, each clause a disjunction of literals (variables or their negations).

Definition (3-SAT). The restricted problem where every clause has exactly 3 literals:

3-SAT = {φ : φ \in SAT and every clause of φ has exactly 3 literals} .

The tableau encoding

Given a language $L \in NP$ , let $M$ be a nondeterministic Turing machine (as defined in 42.04.01) that decides $L$ in time $n^{k}$ . For input $x$ of length $n$ , the computation tableau is an $n^{k} \times n^{k}$ grid. The Cook-Levin construction builds a Boolean formula $φ_{x}$ that encodes this tableau.

Variables. For each cell $(i, j)$ and each possible content $s$ (tape symbol or state-symbol pair), introduce a variable $T_{i, j, s}$ meaning "cell $(i, j)$ contains symbol $s$ ."

Clauses. The formula $φ_{x} = φ_{cell} \land φ_{start} \land φ_{accept} \land φ_{move}$ where:

$φ_{cell}$ : each cell contains exactly one symbol (at-least-one and at-most-one constraints),
$φ_{start}$ : row 0 encodes the start configuration (input $x$ on the tape, head at position 0, start state),
$φ_{accept}$ : some row contains an accept state,
$φ_{move}$ : the contents of each $2 \times 3$ window of cells are consistent with the transition function of $M$ .

The size of $φ_{x}$ is $O (n^{2 k})$ , polynomial in $∣ x ∣$ .

Counterexamples to common slips

"NP-complete means the problem has no polynomial algorithm." We do not know whether P = NP. NP-completeness means the problem is as hard as any NP problem, but a polynomial algorithm might exist — finding one (or proving none exists) would resolve the P vs NP question.
"NP means 'not polynomial'." NP stands for "nondeterministic polynomial time" — the class of problems solvable in polynomial time by a nondeterministic machine. Many NP problems (like sorting) are also in P.
"The Cook-Levin theorem proves P does not equal NP." The theorem proves SAT is NP-complete. It does not resolve P vs NP. It shows that resolving P vs NP can be done by studying any single NP-complete problem.

Key theorem with proof Intermediate+

Theorem (Cook-Levin). SAT is NP-complete.

Proof. We show (1) SAT is in NP and (2) every language in NP reduces to SAT.

(1) A certificate for $φ \in SAT$ is a satisfying assignment $a$ . The verifier evaluates $φ$ on $a$ in polynomial time. So $SAT \in NP$ .

(2) Let $L \in NP$ . There exists a nondeterministic Turing machine (as defined in 42.04.01) $M$ deciding $L$ in time $n^{k}$ . For input $x$ of length $n$ , construct $φ_{x}$ as described above. The construction runs in $O (n^{2 k})$ time.

$φ_{x}$ is satisfiable iff $M$ has an accepting computation on $x$ . If $M$ accepts $x$ , the accepting tableau provides a satisfying assignment for $φ_{x}$ (set $T_{i, j, s}$ to true exactly when cell $(i, j)$ contains $s$ in the accepting computation). If $φ_{x}$ is satisfiable, the satisfying assignment describes a valid tableau: the cell, start, and move constraints guarantee it represents a legal computation of $M$ , and the accept constraint guarantees the computation accepts. So $x \in L$ iff $φ_{x} \in SAT$ .

The function $x \mapsto φ_{x}$ is computable in polynomial time, so $L \leq_{p} SAT$ . $□$

Bridge. The Cook-Levin theorem is the foundational reason NP-completeness is a meaningful concept: there exists a single "universal" problem (SAT) to which all NP problems reduce. This builds toward the web of NP-complete problems in 47.02.03, where reductions from SAT establish hardness for combinatorial problems like CLIQUE and VERTEX-COVER. The central insight is that the tableau encoding is the bridge between computation (a machine processing symbols over time) and logic (a formula asserting the existence of a valid computation). This is exactly the connection that appears again in the PCP theorem of 47.03.06, where the tableau is probabilistically checked, and it generalises the encoding idea from the halting problem of 42.04.02. Putting these together yields the modern understanding of intractability: NP-complete problems are not just hard individually but are polynomial-time interreducible, forming a single equivalence class of difficulty.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Describe the four components of the Cook-Levin formula $φ_{x} = φ_{cell} \land φ_{start} \land φ_{accept} \land φ_{move}$ . For each, state what property of the tableau it encodes and how many clauses it uses.

Answer

$φ_{cell}$ : each cell $(i, j)$ contains at least one symbol ( $⋁_{s} T_{i, j, s}$ ) and at most one symbol ( $\neg T_{i, j, s} \lor \neg T_{i, j, s^{'}}$ for $s \neq = s^{'}$ ). Uses $O (n^{2 k} \cdot ∣Γ ∣^{2})$ clauses where $∣Γ∣$ is the number of possible cell contents.

$φ_{start}$ : row 0 encodes the initial configuration — $T_{0, 0, q_{start}}$ (head at position 0 in start state), $T_{0, j, x_{j}}$ for $0 \leq j < n$ (input symbols), $T_{0, j, ⊔}$ for $n \leq j < n^{k}$ (blank tape). Uses $O (n^{k})$ clauses.

$φ_{accept}$ : some cell in the tableau contains the accept state — $⋁_{i, j} T_{i, j, q_{accept}}$ . Uses $O (n^{2 k})$ clauses.

$φ_{move}$ : for each $2 \times 3$ window centred on the head position, the contents are consistent with some transition of $M$ . Each window generates $O (∣ δ ∣)$ clauses where $δ$ is the transition function. Uses $O (n^{2 k} \cdot ∣ δ ∣)$ clauses.

Exercise 6 (hard, symbolic).

Prove that the move constraint $φ_{move}$ correctly enforces that the tableau represents a valid computation. Specifically, show that any $2 \times 3$ window that is consistent with the transition function guarantees global consistency.

Hint

The head position and state propagate locally: at most one cell in each row contains a state. A $2 \times 3$ window captures the entire effect of one transition.

Answer

In each row, exactly one cell $(i, j)$ contains a state (since $M$ has one head). The transition function $δ (q, s) = (q^{'}, s^{'}, D)$ means: in state $q$ reading symbol $s$ , write $s^{'}$ , move to state $q^{'}$ , and shift the head by $D \in {L, R}$ . A $2 \times 3$ window with the state cell at position $(i, j)$ in the centre captures cells $(i, j - 1), (i, j), (i, j + 1)$ in row $i$ and $(i + 1, j - 1), (i + 1, j), (i + 1, j + 1)$ in row $i + 1$ . The window enforces: row $i + 1$ has the same tape contents as row $i$ except at position $j$ (which changes from $s$ to $s^{'}$ ), and the state in row $i + 1$ is at position $j + D$ . Since every cell not near the head is unchanged between rows, and the head's effect is captured by the window, global consistency follows from local consistency on all windows. Rubric: full credit for the argument that the $2 \times 3$ window is a complete local check.

Lean formalization Intermediate+

Mathlib has Computability.TuringMachine with basic TM definitions and halting predicates, but it does not define NP, polynomial-time reductions, SAT as a complexity-theoretic problem, or NP-completeness. The foundational gap is the absence of Complexity.NP as a class of languages, Complexity.Reduction for polynomial-time many-one reductions, and the Cook-Levin construction that converts a TM computation into a Boolean formula. The tableau encoding with its cell, start, accept, and move constraints has no formalisation. This unit ships without a lean_module.

Advanced results Master

Three results extend the Cook-Levin theorem.

Theorem 1 (Cook's theorem for circuit-SAT). The circuit satisfiability problem (CIRCUIT-SAT) is NP-complete.

The proof encodes the computation tableau directly as a Boolean circuit rather than a CNF formula. Each row of the tableau is computed from the previous row by a fixed circuit that checks the $2 \times 3$ windows. The overall circuit has polynomial size and is satisfiable iff the TM accepts. CIRCUIT-SAT is sometimes used as the starting point for NP-completeness proofs instead of SAT because the circuit model is closer to hardware ^{[Arora & Barak §2.3]}.

Theorem 2 (Berman-Hartmanis conjecture). All known natural NP-complete problems are polynomial-time isomorphic (i.e., related by polynomial-time bijections with polynomial-time inverses).

This conjecture (1977) states that all NP-complete sets are "essentially the same" up to polynomial-time relabelling. It has been verified for all natural NP-complete problems but remains unproven in general. A consequence is that if the conjecture holds and P $\neq =$ NP, then no sparse set (a set with only polynomially many strings of each length) is NP-complete.

Theorem 3 (NP-completeness of 3-SAT). 3-SAT is NP-complete.

The reduction from SAT to 3-SAT uses the gadget construction from the worked example. Each clause of length $k > 3$ is split into $k - 2$ clauses of length 3 using $k - 3$ auxiliary variables. The reduction preserves satisfiability and runs in polynomial time. Since SAT is NP-complete and 3-SAT is in NP, transitivity gives NP-completeness of 3-SAT ^{[Sipser §7.5]}.

Synthesis. The Cook-Levin theorem is the foundational reason NP-completeness is a coherent and useful concept: it provides a single universal bottleneck problem to which all NP problems reduce. The central insight is that computation can be encoded as logic — the tableau construction translates "does this machine accept?" into "is this formula satisfiable?" This builds toward the entire theory of NP-completeness reductions, where hundreds of practical problems are shown to be NP-complete by chains of reductions from SAT. The bridge is that the tableau encoding appears again in the PCP theorem, where it is made robust to probabilistic checking, and this is exactly what connects computational hardness to inapproximability results. Putting these together with the polynomial hierarchy of 47.02.04 yields the modern map of computational complexity: a landscape of difficulty levels connected by reductions.

Full proof set Master

Proposition 1 (Cook-Levin: SAT is NP-complete). $SAT$ is NP-complete.

Proof. Membership: $SAT \in NP$ because a satisfying assignment is a polynomial-length certificate verifiable in polynomial time by evaluating the formula.

Hardness: Let $L \in NP$ via NDTM $M$ running in time $t = n^{k}$ . Construct $φ_{x}$ encoding the computation tableau. The formula has four parts:

$φ_{cell} = ⋀_{i, j} [(⋁_{s} T_{i, j, s}) \land ⋀_{s \neq = s^{'}} (\neg T_{i, j, s} \lor \neg T_{i, j, s^{'}})]$

$φ_{start} = T_{0, 0, q_{0} \cdot x_{0}} \land ⋀_{j = 1}^{n - 1} T_{0, j, x_{j}} \land ⋀_{j = n}^{t - 1} T_{0, j, ⊔}$

$φ_{accept} = ⋁_{0 \leq i < t} ⋁_{0 \leq j < t} T_{i, j, q_{accept}}$

$φ_{move} = ⋀_{i, j} ⋁_{legal windows} ⋀_{cells in window} T_{i, j, s}$

The construction time is $O (n^{2 k})$ . If $M$ accepts $x$ , the accepting tableau satisfies $φ_{x}$ . If $φ_{x}$ is satisfiable, the satisfying assignment describes a valid accepting computation of $M$ on $x$ . So $x \in L ⟺ φ_{x} \in SAT$ . $□$

Proposition 2 (SAT reduces to 3-SAT). There exists a polynomial-time reduction from SAT to 3-SAT.

Proof. Given a CNF formula $φ$ with clauses $C_{1}, \dots, C_{m}$ , for each clause $C_{i}$ of length $k_{i}$ :

If $k_{i} = 1$ , say $C_{i} = (ℓ)$ , replace with $(ℓ \lor p \lor q) \land (ℓ \lor \neg p \lor q) \land (ℓ \lor p \lor \neg q) \land (ℓ \lor \neg p \lor \neg q)$ for new variables $p, q$ .
If $k_{i} = 2$ , say $C_{i} = (ℓ_{1} \lor ℓ_{2})$ , replace with $(ℓ_{1} \lor ℓ_{2} \lor p) \land (ℓ_{1} \lor ℓ_{2} \lor \neg p)$ for new variable $p$ .
If $k_{i} = 3$ , keep as is.
If $k_{i} > 3$ , say $C_{i} = (ℓ_{1} \lor \dots \lor ℓ_{k})$ , replace with $(ℓ_{1} \lor ℓ_{2} \lor z_{1}) \land (\neg z_{1} \lor ℓ_{3} \lor z_{2}) \land \dots \land (\neg z_{k - 3} \lor ℓ_{k - 1} \lor ℓ_{k})$ for new variables $z_{1}, \dots, z_{k - 3}$ .

Each gadget introduces $O (k_{i})$ new variables and clauses. Total size is $O (\sum k_{i}) = O (∣ φ ∣)$ . The reduction preserves satisfiability by the gadget correctness argument. $□$

Connections Master

42.04.01 — The Turing machine model is the computational foundation for the Cook-Levin tableau encoding; every NP computation is a TM computation, and the tableau captures its full history.
47.02.01 — P, NP, and polynomial-time reductions are defined in 47.02.01; the Cook-Levin theorem uses these definitions to prove the existence of NP-complete problems.
47.02.03 — Classic NP-complete problems (CLIQUE, VERTEX-COVER, HAM-CYCLE) are proved NP-complete by reduction from SAT or 3-SAT, using the NP-completeness established here.
47.03.02 — The Karp-Lipton theorem uses the NP-completeness of SAT to show that polynomial-size circuits for NP would collapse the polynomial hierarchy.

Historical & philosophical context Master

The Cook-Levin theorem was proved independently by Stephen Cook (1971) and Leonid Levin (1973). Cook's paper "The Complexity of Theorem-Proving Procedures" showed that SAT is NP-complete by encoding Turing machine computations as Boolean formulas. Levin's paper, published in Russian, proved the same result using a different but equivalent construction ^{[Arora & Barak §2.3]}.

Richard Karp's 1972 paper "Reducibility among Combinatorial Problems" showed that 21 fundamental combinatorial problems (including CLIQUE, VERTEX-COVER, HAM-CYCLE, and SUBSET-SUM) are all NP-complete by building chains of reductions from SAT. This transformed NP-completeness from a theoretical curiosity into a practical tool: any new problem could be shown intractable (assuming P $\neq =$ NP) by reducing a known NP-complete problem to it.

The philosophical significance of NP-completeness is that it reveals a deep unity among seemingly unrelated problems. Satisfiability of Boolean formulas, optimal tour planning, graph colouring, and scheduling are all "the same problem" in the sense that they are polynomial-time interreducible. This suggests that the boundary between tractable and intractable is a fundamental feature of computation itself, not an artifact of any particular problem formulation ^{[Sipser §7.4]}.

Bibliography Master

@inproceedings{cook1971complexity,
  author    = {Cook, Stephen A.},
  title     = {The Complexity of Theorem-Proving Procedures},
  booktitle = {Proceedings of the 3rd Annual ACM Symposium on Theory of Computing},
  pages     = {151--158},
  year      = {1971},
}
@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{arora2009,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{karp1972reducibility,
  author  = {Karp, Richard M.},
  title   = {Reducibility among Combinatorial Problems},
  journal = {Complexity of Computer Computations},
  pages   = {85--103},
  year    = {1972},
  publisher = {Plenum Press},
}

Prerequisites

47.02.01
42.04.01

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4 (NP-completeness as the hardest problems in NP, the Cook-Levin theorem showing SAT is NP-complete, reductions between NP-complete problems)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4-7.5 (formal NP-completeness definition, Cook-Levin proof via tableau-to-circuit reduction, SAT to 3-SAT to CLIQUE reductions); Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §2.3 (the Cook-Levin theorem via tableau construction)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4-7.5; Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §2.3-2.5 (full tableau construction, circuit-SAT to SAT reduction, Ladner's theorem, structure of NP-complete problems)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 7.4 defines a language $B$ as NP-complete if (i) $B \in NP$ and (ii) every language $A \in NP$ is polynomial-time reducible to $B$ ( $A \leq_{p} B$ ); the Cook-Levin theorem proves that $SAT = {φ : φ is a satisfiable Boolean formula}$ is NP-complete by encoding the computation tableau of a nondeterministic Turing machine running in time $n^{k}$ as a Boolean formula of size $O (n^{2 k})$ ; section 7.5 reduces SAT to 3-SAT via the "gadget" construction splitting clauses with auxiliary variables, and reduces 3-SAT to CLIQUE, establishing the web of NP-complete problems.
Arora, S. & Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 2 presents the Cook-Levin theorem using the tableau method: for $L \in NP$ witnessed by an $n^{k}$ -time NDTM $M$ , construct a Boolean formula $φ_{x}$ of size $O (n^{2 k})$ that is satisfiable iff $M$ accepts $x$ ; the formula encodes each cell of the $n^{k} \times n^{k}$ tableau with variables $T_{i, j, s}$ ("cell $(i, j)$ contains symbol $s$ "), the row transition constraints as a local consistency check on $2 \times 3$ windows, and the start and accept conditions; Ladner's theorem (§2.4) shows that if $P \neq = NP$ then there exist NP-intermediate languages neither in P nor NP-complete.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m