NP-completeness — Cook's theorem (SAT is NP-complete), reduction: Visual walkthrough

Step 0 — The words we are allowed to use

Before any symbol appears, here is every ingredient in plain language.

Definition The vocabulary, from zero

A Turing machine is an imaginary computer: an infinite paper tape divided into cells, a head that sits on one cell and can read/write one symbol, and a state (think: the machine's current "mood", like a gear a car is in). At each tick it looks at the symbol under the head + its current state, then it writes a symbol, moves the head left or right by one cell, and switches to a new state. That's the whole machine.
A machine's states form a finite set $Q$ . Two of them are distinguished and named up front: $q_{0} \in Q$ , the start state (the mood the machine boots in), and $q_{accept} \in Q$ , the accepting state (reaching it means "yes, accept"). We will use exactly these two special names later, so meet them now.
A Nondeterministic Turing machine (NTM) is the same, but at each tick it may have several legal moves and is allowed to "guess" one. It accepts if some sequence of guesses reaches $q_{accept}$ .
A poly-time NTM is an NTM that always halts within $p (n)$ steps, where $p$ is some fixed polynomial (like $p (n) = n^{2}$ or $n^{3} + 5$ ) and $n$ is the input length. "Polynomial" is the formal meaning of "fast / efficient". Every problem $L \in$ NP is, by definition, run by exactly such a machine.
A Boolean variable is a lightswitch: it is either TRUE (on) or FALSE (off). Nothing else.
3-SAT / SAT asks: given a formula of these switches wired with AND ( $\land$ = all must be on), OR ( $\lor$ = at least one on), NOT ( $\neg$ = flip), can we flip switches so the whole thing lights up TRUE?
A certificate is a proposed answer we can check quickly. For an NTM, the certificate is "the lucky sequence of guesses".

Cook's job: take any problem that has such a quick checker (any $L \in$ NP, run by a poly-time NTM $M$ ), and any input $w$ , and manufacture a Boolean formula that lights up exactly when $M$ can accept $w$ .

The strategy in one line: freeze the entire run of $M$ into a rectangular grid of cells, name every cell with switches, and write down local rules that force the grid to be a legal, accepting run.

Step 1 — Freeze the whole run into a grid (the tableau)

WHAT we did: replaced "a movie of the machine running" with "a single still photo of all frames stacked". WHY: a movie is unbounded and slippery; a fixed finite grid can be described by a fixed finite number of switches. Finiteness is the entire game — SAT formulas are finite objects. And because $p$ is a polynomial, that finite grid is only polynomially large. PICTURE: below, time flows downward; each row is the tape at one instant. Column $0$ is the left wall; the amber cell marks where the head is standing.

Figure — NP-completeness — Cook's theorem (SAT is NP-complete), reduction

Step 2 — What must a single cell record?

Each cell of the grid is not just a tape letter. It must also say "is the head here, and if so, in which state?"

WHAT: gave each cell a small fixed menu $C$ of possible contents. WHY: to encode a configuration we need three facts — the tape letter, the head position, the state. Bundling "head + state" into special contents lets a single grid carry all three. PICTURE: one column of the menu $C$ ; a plain cell shows only a letter, a head-cell shows the little "(state, letter)" badge.

Step 3 — Name every cell-content with a switch (the variables)

Now the leap that connects machines to Boolean logic.

Counting the switches (this is where "polynomial" is born): $rows (p (n) + 1) \times cols (p (n) + 1) \times constant menu size ∣ C ∣ = O (p (n)^{2}) .$ Term by term: rows times columns gives $p (n)^{2}$ ; $∣ C ∣$ is a fixed constant (doesn't grow with input), so it vanishes into big- $O$ . Because $p$ is a polynomial, the variable count is polynomial in $n$ . ✔

WHAT: turned "the grid is filled in like this" into "these switches are ON, those are OFF". WHY: SAT only understands switches. A filled tableau and a truth assignment are now the same information in two languages — this bijection is the heart of the proof. PICTURE: one grid cell exploded into its stack of candidate switches; exactly one glows.

Step 4 — Rule A: every cell holds exactly one thing

A truth assignment could be nonsense — it might turn ON two switches for the same cell ("this cell is both 0 and 1"). We forbid that.

WHAT: pinned each cell down to a single legal content. WHY: without this, "satisfiable" could be won by an incoherent grid, and the equivalence to a real run would break. PICTURE: two switches ON in one cell = a red ✗; exactly one ON = a green ✓.

Step 5 — Rules B & C: correct start, and reach acceptance

WHAT: forced the run to begin correctly and to end in success. WHY: a valid computation must start from the true input (not a convenient fantasy) and must actually accept. Start pins the boundary; accept is the goal. PICTURE: top row locked to $w$ ; anywhere a head-cell turns amber "accept", the whole run is crowned.

Step 6 — Rule D: legal moves via the $2 \times 3$ window (the clever core)

The remaining danger: rows might not follow from one another by $M$ 's rules — teleporting heads, symbols changing far from the head, illegal state jumps. We must forbid all of that. The genius is that it suffices to check tiny local patches.

The two kinds of legal window, written as switches

Let a window's six cells carry contents named as follows (top row = time $i$ , bottom = time $i + 1$ ): $a d b e c f$ A specific assignment of contents to $(a, b, c, d, e, f)$ is one pattern. We now list which six-tuples are legal, and turn "this window equals this pattern" into a Boolean formula.

Definition The legal-pattern set

$L$ (identity + active transition) A six-tuple $P = (a, b, c, d, e, f)$ is legal ( $P \in L$ ) if it is one of two kinds:

Identity patch — no head in the top row (none of $a, b, c$ is a $(q, \cdot)$ badge). Then nothing under this window changed, so the middle cell copies down: $e = b$ , and $d, f$ obey the copy/neighbour rules. Example (all plain): $(0, 1, 0, 0, 1, 0)$ — the bottom repeats the top. ✔
Active transition patch — a head sits at $b$ (so $b = (q, β)$ for some state $q$ and symbol $β$ ). Then the bottom row must match $M$ 's transition rule for $(q, β)$ . If $M$ has the rule "in state $q$ reading $β$ : write $γ$ , move right, go to $q^{'}$ ", the legal bottom is $d = a$ , $e = γ$ , $f = (q^{'}, c)$ . If instead the rule moves left, the head lands at $d = (q^{'}, a)$ , $e = γ$ , $f = c$ . Example (write $0$ , move right, go to $q^{'}$ ): $(_, (q, 1), 0,_, 0, (q^{'}, 0))$ . ✔
Head at $a$ or $c$ (edge of window): handled symmetrically — if the head is at $a$ and moves right it may enter $b$ ; the finite list $L$ enumerates every such combination once and for all.

Because $∣ Q ∣$ , $∣Γ∣$ , and the number of transition rules are all constants (independent of $n$ ), the set $L$ is a finite constant-size list of legal six-tuples. Say $∣ L ∣ = c_{0}$ , a constant.

WHAT: replaced one impossible-to-check global rule ("this is a valid run") with a per-window OR over an explicit finite list $L$ of allowed six-tuples — each tuple being either a copy (head elsewhere) or a rule application (head present). WHY: global legality has no small formula, but each window has only $6$ cells and $c_{0}$ candidate patterns — a constant-size condition we can list explicitly.

PICTURE: identity patch (green copy) vs active transition patch (green rule-move) vs an illegal teleport (red ✗, matches no $P \in L$ ).

Step 7 — Assemble, and read the equivalence both directions

WHY this exact conjunction — the two-way equivalence. This is the payoff we must argue explicitly, not just assert:

( $\Rightarrow$ ) If $M$ accepts $w$ : there exists an accepting run. Fill the tableau with that run and switch on exactly the matching $x_{i, j, s}$ . Then $ϕ_{cell}$ holds (each real cell has one content), $ϕ_{start}$ holds (a real run starts from $w$ in state $q_{0}$ ), $ϕ_{move}$ holds (each real step obeys $M$ , so each window matches some $P \in L$ ), and $ϕ_{accept}$ holds (an accepting run reaches $q_{accept}$ ). All four ⇒ $ϕ_{M, w}$ is satisfiable.
( $\Leftarrow$ ) If $ϕ_{M, w}$ is satisfiable: take any satisfying assignment. $ϕ_{cell}$ ⇒ it describes a well-defined grid (one content per cell). $ϕ_{start}$ ⇒ row $0$ is the true start configuration (one head, state $q_{0}$ , input $w$ ). $ϕ_{move}$ ⇒ every window is legal, so row $i + 1$ follows from row $i$ by an actual transition of $M$ — inductively the whole grid is a legal run with one head per row. $ϕ_{accept}$ ⇒ some row contains $q_{accept}$ , so the run accepts. Hence $M$ does accept $w$ .

WHY the whole thing is a legal reduction — the size/time bound. Summing the pieces: $∣ ϕ_{cell} ∣, ∣ ϕ_{start} ∣, ∣ ϕ_{accept} ∣, ∣ ϕ_{move} ∣$ are each $O (p (n)^{2})$ (Steps 3–6), so $∣ ϕ_{M, w} ∣ = O (p (n)^{2}) = poly (n)$ , and it is built by a simple deterministic scan over the grid in $poly (n)$ time. A polynomial-size, polynomial-time-computable map is exactly what a Polynomial-time reduction requires.

Putting it together: $w \in L ⟺ M accepts w ⟺ ϕ_{M, w} \in SAT .$ Since this works for every $L \in$ NP and $ϕ_{M, w}$ is built in poly time, every NP problem reduces to SAT: SAT is NP-hard. With SAT $\in$ NP (just plug in the assignment and evaluate), SAT is NP-complete, the anchor for Karp's 21 NP-complete problems, Independent Set, Vertex Cover, Clique, and the whole P vs NP problem landscape. $■$

Degenerate & edge cases (never leave the reader stranded)

Worked example The empty / trivial cases

$w = ε$ (empty input), $n = 0$ : the grid still exists with $p (0) + 1$ rows/cols; $ϕ_{start}$ just fills row $0$ with the start state $q_{0}$ 's head-badge on cell $0$ and blanks elsewhere. Nothing breaks — a degenerate tableau is still a valid tableau.
$M$ rejects on every guess: then no legal accepting tableau exists, so no assignment can satisfy $ϕ_{accept}$ together with the others. $ϕ_{M, w}$ is unsatisfiable — exactly matching " $w \in / L$ ". The equivalence holds in the negative direction too.
Head tries to move left off cell 0: thanks to the one-sided tape (Step 0), the transition rulebook simply has no such move, so no six-tuple $P \in L$ permits it — $ϕ_{move}$ forbids it automatically, and no negative column is ever referenced.
Deterministic $M$ : a special case where, at each configuration, exactly one legal window pattern applies. The construction is identical; nondeterminism just allows several patterns in $L$ to fit, hence several satisfying assignments.

The one-picture summary

The single figure above compresses the whole journey: an arbitrary NP problem's poly-time NTM $M$ + input $w$ → a stacked tableau → renamed as switches → clamped by four rule-groups → a Boolean formula whose satisfiability is acceptance.

Recall Feynman retelling — say it back in plain words

Imagine any fast-checkable problem is run by a guessing machine that always finishes within a polynomial number of steps. I want to catch that machine's whole life story in one snapshot, so I lay every moment of its run as a row in a big square table — time going down, tape going across; the tape has a hard wall on the left at cell 0 (no negative cells), and because the machine is polynomial-time, the table is only polynomially big. In each little box I write what's there: a symbol, or "the head is here in such-and-such mood." Now I give every possible "this box says X" its own on/off switch. A filled-in table and a pattern of switches are the same thing said two ways. Then I write four kinds of rules as switch-logic: (A) no box says two contradictory things (each cell holds exactly one content); (B) the first row is the honest starting picture — the input string sitting on the tape, the head parked on cell 0 in the start state $q_{0}$ , which also plants the single head we'll carry down; (C) somewhere in the table the head shows up in the "accept" state $q_{accept}$ , so the run actually says yes; and (D) — the clever bit — every tiny 2-by-3 patch of neighbouring boxes must match one entry in a short fixed list of legal patches: either the bottom just copies the top (no head present), or, if a head is present, the bottom is exactly what that transition rule produces. Each patch check is a small OR over that constant list, and each list entry is just six switches AND-ed; there are about (table area) patches, so the whole rule stays polynomial. Because one step only touches nearby boxes, these little local checks are enough to make the entire run legal, and they keep "exactly one head per row" true all the way down. AND all four rules into one giant formula whose total size is polynomial. Flipping the switches to light it up is exactly the same as the machine finding a way to say yes — and I argued it both ways: a real accepting run gives a satisfying assignment, and any satisfying assignment decodes back into a real accepting run. So if you had a magic fast SAT-solver, you'd solve every checkable problem in the world. That's why SAT is the master key.

Recall Self-test

Why is a $2 \times 3$ window enough to guarantee the whole tableau is a legal run? ::: Because one step of the head only affects the cell under it and its two neighbours, so a cell at time $i + 1$ depends only on 3 cells at time $i$ ; checking every such patch matches a legal pattern forces global legality and preserves one-head-per-row. How many Boolean variables are used, and why does that matter? ::: $O (p (n)^{2})$ (rows $\times$ columns $\times$ constant menu $∣ C ∣$ ); since $p$ is a polynomial this count is polynomial ⇒ the reduction is polynomial-time, which is what NP-hardness requires. How large is $ϕ_{move}$ and why? ::: $O (p (n)^{2})$ : about $p (n)^{2}$ windows, each a constant number $c_{0}$ of legal patterns, each pattern a $6$ -literal conjunction; constants vanish into big- $O$ . How do we forbid the head moving left off cell 0? ::: We use a one-sided tape with a left wall at cell 0, so no transition rule (and hence no legal window pattern $P \in L$ ) represents such a move — no negative column is ever needed. If $ϕ_{M, w}$ is unsatisfiable, what does it mean for $w$ ? ::: No legal accepting tableau exists, so $M$ never accepts $w$ , i.e. $w \in / L$ .