Cook–Levin tableau · TM run as SAT formula

This is the founding theorem of NP-completeness. Before Cook (1971) and Levin (1973) independently proved it, NP existed as a class but no problem was known to be "the hardest". Cook–Levin pinned the title on SAT and started the chain reaction that today covers thousands of problems — 3SAT, CLIQUE, VERTEX-COVER, HAMPATH, TSP, SUBSET-SUM, 3-COLOR, INTEGER-PROGRAMMING, …

The key insight: a Boolean formula can simulate a TM. Any problem in NP has a polynomial-time verifier; the verifier is a TM; encode its computation as a formula. That formula is satisfiable iff some certificate makes the verifier accept — which is exactly the NP membership question.

Big consequence: a polynomial-time SAT solver would collapse NP to P, breaking modern cryptography (RSA, AES are not directly NP-hard, but most public-key assumptions live in or near NP). This is why the P vs NP question is the most famous open problem in computer science.

Pick L ∈ NP with poly-time verifier V. By definition:

• x ∈ L ⇔ ∃ certificate c (|c| ≤ poly(|x|)) with V(x, c) accepting.
• V runs for at most n^k steps, where n = |x|.

So the entire run of V uses at most n^k tape cells in at most n^k time steps. We arrange this as a grid:

Each cell becomes a set of Boolean variables: x_t,p,s = "cell (t,p) holds symbol s". The variable count is n^k · n^k · |Γ ∪ Q| = polynomial.

We assemble φ_x = φ_cell ∧ φ_start ∧ φ_accept ∧ φ_move.

Suppose L is SUBSET-SUM and the verifier V takes n bits and runs in n² steps:

Polynomial — but the constant matters. In practice, modern SAT solvers handle problems with millions of variables. The Cook–Levin reduction is theoretical; tighter reductions (e.g. directly to 3SAT) are used for practical NP-completeness work.

From Cook–Levin, every other NP-complete proof follows a fixed pattern: "reduce SAT (or 3SAT) to my problem."

• 3SAT · convert each clause of φ_x into 3-literal clauses with auxiliary variables (Problem 26).
• CLIQUE · vertices = literal occurrences; edge = compatible literals across different clauses (Problem 27).
• VERTEX-COVER · complement of CLIQUE on the complement graph (Problem 28).
• SUBSET-SUM, HAMPATH, 3-COLOR, TSP, SCHEDULING — all via increasingly creative reductions from 3SAT.

Karp's 1972 paper added 21 problems to the family in one stroke. Garey & Johnson's 1979 book catalogued hundreds.

1. "The tableau is the SAT formula." No — the tableau is a thought picture. The formula encodes constraints about the tableau using Boolean variables.
2. Confusing rows with tape, columns with time. The convention here is rows = time, columns = position. Pick one and stick with it.
3. Encoding wide TMs. If the TM uses |Γ| = 100 symbols, each cell needs 100 variables. Still polynomial — but watch the constants.
4. Forgetting φ_cell. Without "exactly one symbol per cell" clauses, a satisfying assignment could put two symbols in one cell. The construction breaks.
5. "This proves SAT is in NP." SAT ∈ NP needs a separate (easy) argument: guess the assignment, verify. Cook–Levin proves the hardness direction.

• Q1. Why a 2×3 window?
  A TM transition affects only the head cell and possibly its neighbours, between two consecutive time steps. 2 rows × 3 columns captures one transition.
• Q2. Why polynomial size?
  Tableau is n^k×n^k = poly cells. Each cell has |Γ|+|Q| Boolean variables (= which symbol/state). Formula size = polynomial in input size.
• Q3. What's the SAT formula's role?
  φ_x is satisfiable iff some valid accepting tableau exists iff some certificate c makes V(x, c) accept iff x ∈ L.
• Q4. Why doesn't the same trick work for EXPTIME?
  An EXPTIME verifier runs for 2ⁿ steps, producing an exponential-size tableau and an exponential-size formula. That formula is satisfiable iff x ∈ L, but it's too big to write down in polynomial time — so we don't get an NP-style reduction to SAT.
• Q5. Could SAT have a sub-exponential algorithm?
  Open. The Exponential Time Hypothesis (ETH) conjectures 3SAT cannot be solved in 2^o(n). Plenty of refined results assume ETH; no proof either way.

Total time: 12 minutes.

• (1 min) Hook: "Why is SAT special?" Because every NP problem can dress up as a SAT instance.
• (2 min) Define the tableau. Pick conventions (rows=time, columns=tape).
• (3 min) Walk through the four clause families. Spend the most time on φ_move and the 2×3 window.
• (3 min) Run the visualization. Pause at the moment a 2×3 window highlights.
• (2 min) Do a size sanity check: "For an n=100 input, how many cells?" Get the audience to compute.
• (1 min) Forward link: Karp's 21 problems all follow from this single reduction.