NP-Completeness and Cook-Levin

A decision problem is a language $L \subseteq \{0,1\}^*$, and $L \in \text{NP}$ means membership in $L$ can be verified in polynomial time given a suitable certificate. Formally, $L \in \text{NP}$ if there is a polynomial-time algorithm $V(x, c)$ and a polynomial $p$ such that

Equivalently, $L$ is decided by some nondeterministic Turing machine running in polynomial time, which is why the class is called NP (Nondeterministic Polynomial time). A problem $L$ is NP-hard if every language $L' \in \text{NP}$ reduces to $L$ via a polynomial-time reduction, written $L' \le_p L$. A polynomial-time reduction from $L'$ to $L$ is a polynomial-time computable function $f$ such that $x \in L' \iff f(x) \in L$. NP-hardness alone says nothing about whether $L$ itself is in NP — it could be far harder. A problem is NP-complete if it is both NP-hard and a member of NP itself. NP-complete problems are exactly the hardest problems inside NP: they sit at the top of the polynomial-time-reducibility ordering restricted to NP. The reason NP-completeness is such a load-bearing concept is transitivity. If $L_1 \le_p L_2$ and $L_2 \le_p L_3$, then $L_1 \le_p L_3$, because composing two polynomial-time functions yields a polynomial-time function. So once a single problem $L_0$ is known to be NP-complete, proving a new problem $L$ NP-complete only requires (1) showing $L \in \text{NP}$, and (2) exhibiting a polynomial-time reduction $L_0 \le_p L$ for some already-known NP-complete $L_0$ — not for every problem in NP. This is the entire methodology used in Classic NP-Complete Problems. But that bootstrapping needs a starting point: some $L_0$ proven NP-complete directly, from the definition, with no shortcut available. That is exactly what the Cook-Levin theorem supplies, and it is why the theorem is foundational rather than merely another example.

Boolean satisfiability (SAT). An instance is a Boolean formula $\varphi$ over variables $x_1, \dots, x_n$, built from AND, OR, and NOT. The question: does some assignment of TRUE/FALSE to the variables make $\varphi$ evaluate to TRUE? SAT is clearly in NP — a satisfying assignment is a certificate, and checking that it satisfies $\varphi$ takes time linear in the size of $\varphi$.

The Cook-Levin theorem. SAT is NP-complete. The membership in NP is the easy half; the substance is proving SAT is NP-hard — that every language in NP reduces to SAT in polynomial time. The proof strategy: take an arbitrary language $L \in \text{NP}$. By definition there is a nondeterministic Turing machine $M$ deciding $L$ in time $p(n)$ for some polynomial $p$, on inputs of length $n$. We must build, for each input $x$, a Boolean formula $\varphi_x$ — computable from $x$ in time polynomial in $|x|$ — such that

The construction encodes the entire space-time history of $M$'s computation on $x$ as a grid of Boolean variables called a tableau, and writes down clauses that force any satisfying assignment to correspond to a valid, accepting run of $M$.

The tableau. Picture a $p(n) \times p(n)$ grid: rows indexed by time steps $t = 0, \dots, p(n)$, columns indexed by tape positions $j = 1, \dots, p(n)$ (since $M$ runs in time $p(n)$ it can only reach $p(n)$ tape cells). Each cell $(t, j)$ of the grid holds the tape symbol at position $j$ at time $t$, plus, for at most one column per row, information about the head position and current state. We introduce a Boolean variable

meaning "at time $t$, cell $j$ holds symbol $s$." Exactly one such variable is true per cell per time step. The formula $\varphi_x$ is the AND of four groups of clauses, each polynomial in size and easy to write down from $M$'s transition table and the input $x$: 1. Cell consistency: each cell has exactly one symbol at each time (at-least-one and at-most-one clauses over the $X_{t,j,s}$ for fixed $t,j$). 2. Start configuration: at $t = 0$, the tape holds $x$, the head is at position 1, and the state is the start state — these are unit clauses fixing specific variables to true. 3. Accept condition: some cell in the final row $t = p(n)$ encodes an accepting state — a clause that is the OR of the relevant variables. 4. Transition consistency: for every $2\times 3$ or $3\times 3$ "window" of cells (a small local neighborhood spanning consecutive time steps), the combination of symbols appearing there must be one that $M$'s transition function allows. Since $M$ moves its head only one step per tick, the value of cell $(t+1, j)$ is fully determined by cells $(t, j-1), (t,j), (t,j+1)$ (this is the crucial locality property enabling a local, hence small, set of constraints). We enumerate, for each such window position, the finite set of allowed local patterns and forbid all others via clauses. Because $M$ is nondeterministic, more than one transition may be legal from a configuration; the tableau does not fix which choice is made — the satisfying assignment picks a particular accepting computation path if one exists. This is exactly why SAT, an existential ("does some assignment satisfy") problem, is the right target for encoding an existential ("does some nondeterministic run accept") computation. ``` function COOK-LEVIN-REDUCE(M, x):

# M: nondeterministic TM deciding L in time p(n); x: input string n := |x| T := p(n) # time bound S := p(n) # tape cells reachable in time T

# 1. Create variables X[t][j][s] for t in 0..T, j in 1..S,

# s ranging over tape alphabet union (state x head-marker) symbols create_variables(T, S, M.symbols) clauses := empty set

# 2. Cell-consistency: exactly one symbol per (t, j) for t in 0..T: for j in 1..S: add_clause( OR_s X[t][j][s] ) # at least one for each pair s != s': add_clause( NOT X[t][j][s] OR NOT X[t][j][s'] ) # at most one

# 3. Start configuration clauses (unit clauses fixing t = 0 row to x,

# blanks, head at position 1, state = start) fix_start_row(clauses, x, M.start_state)

# 4. Accept clause: some cell at t = T encodes an accepting state add_clause( OR_j OR_{s in accepting-symbols} X[T][j][s] )

# 5. Transition-consistency clauses over every local window for t in 0..T-1: for j in 1..S: legal := local_patterns_allowed_by(M, t, j) # finite list forbid_all_patterns_not_in(legal, clauses, t, j) phi := AND of all clauses return phi ``` The reduction runs in time polynomial in $|x|$: the tableau has $O(p(n)^2)$ cells, each with a constant-size alphabet, so there are $O(p(n)^2)$ variables and $O(p(n)^2)$ clauses (each clause touches only a bounded number of variables, since transition rules and the alphabet are fixed, finite pieces of $M$, independent of $n$). Writing down the formula is mechanical, table-lookup work — no simulation of $M$ on $x$ is actually performed during the reduction itself; the reduction only writes constraints that any valid run must obey.

Membership in NP. For SAT, a satisfying assignment $c$ of length $n$ (the number of variables) is the certificate; evaluating $\varphi(c)$ takes $O(|\varphi|)$ time by a single pass substituting truth values and evaluating the AND/OR/NOT tree. So SAT $\in$ NP unconditionally.

Correctness of the reduction (Cook–Levin). We must show $\varphi_x$ is satisfiable if and only if $M$ accepts $x$.

• ($\Leftarrow$) Suppose $M$ accepts $x$ via some sequence of nondeterministic choices, producing an accepting computation history — a sequence of configurations $C_0, C_1, \dots, C_T$ where $C_0$ is the start configuration on $x$, each $C_{t+1}$ follows from $C_t$ by one legal transition of $M$, and $C_T$ is accepting. Set $X_{t,j,s} = \text{true}$ exactly when configuration $C_t$ has symbol $s$ at position $j$. By construction, this assignment satisfies every cell-consistency clause (each cell truly holds one symbol), the start clauses (row 0 matches $x$), the accept clause (row $T$ is accepting), and every transition-consistency clause (each local window reflects an actual legal move of $M$, since $C_{t+1}$ really did follow from $C_t$ that way). Hence $\varphi_x$ is satisfied.

• ($\Rightarrow$) Suppose $\varphi_x$ has a satisfying assignment. Cell-consistency clauses guarantee each grid cell corresponds to a unique symbol, so the assignment defines a well-formed sequence of configurations $C_0, \dots, C_T$. Start clauses force $C_0$ to be the correct initial configuration on $x$. Transition-consistency clauses force every consecutive pair $(C_t, C_{t+1})$ to be related by a transition that $M$'s rules genuinely permit (this is exactly what "forbid all non-legal local patterns" achieves — no satisfying assignment can contain an illegal local window). The accept clause forces $C_T$ to be accepting. So the sequence $C_0, \dots, C_T$ is a genuine accepting run of $M$ on $x$, meaning $M$ accepts $x$.

Both directions rely critically on the locality of Turing-machine transitions: whether cell $(t+1, j)$'s symbol is consistent with its neighbors at time $t$ depends only on a bounded local neighborhood, which is exactly what lets the transition constraints be written as a polynomial number of small, fixed-size clauses rather than needing to reason globally about the whole tape at once.

Size and running time of the reduction. The tableau has $T = p(n)$ rows and $S = p(n)$ columns, giving $O(p(n)^2)$ cells; the alphabet size and the number of states of $M$ are constants independent of $n$, so the number of variables is $O(p(n)^2)$, and each of the four clause groups contributes $O(p(n)^2)$ clauses of constant size. Constructing $\varphi_x$ therefore takes time polynomial in $n$ — specifically $O(p(n)^2)$ up to constants depending on $M$'s alphabet size — which is exactly what "polynomial-time reduction" requires. Since $L \in \text{NP}$ was arbitrary, this shows every language in NP reduces to SAT in polynomial time, i.e., SAT is NP-hard. Combined with SAT $\in$ NP, this proves SAT is NP-complete.

Honest caveats. Cook-Levin does not prove $P \ne NP$; it proves that SAT is a canonical hardest problem within NP, contingent on the (widely believed but unproven) conjecture that P $\ne$ NP. If someone found a polynomial-time SAT solver, that single algorithm — via the same reduction machinery — would yield polynomial-time algorithms for every problem in NP, collapsing P and NP into one class. The theorem is also a worst-case statement: it says nothing about how hard typical or structured SAT instances are, which is why practical SAT solvers can be remarkably fast on real-world instances despite the worst-case hardness — a gap explored in Coping with NP-Hardness.

Reductions are usually illustrated on a small target problem rather than by fully expanding a tableau (which even for tiny machines has hundreds of variables). Here is a concrete trace of the reduction methodology that Cook-Levin makes possible, showing how a second, more human-friendly NP-complete problem — 3-SAT — is derived, and then how a tiny SAT instance is solved, to make the abstract theorem tangible end to end.

Step 1 — From general SAT to 3-SAT. Any clause with more than 3 literals can be split using auxiliary variables. Consider a clause with four literals:

Introduce a fresh variable $y$ and replace it with two 3-literal clauses:

These are equisatisfiable with the original clause: if the original is satisfied by some $\ell_i$ = true, set $y$ accordingly (true if $\ell_1$ or $\ell_2$ is true, false otherwise) to satisfy both parts; conversely any satisfying assignment of the two parts forces at least one $\ell_i$ true. This shows SAT $\le_p$ 3-SAT, extending Cook-Levin's result to the restricted clause form used constantly in later reductions.

Step 2 — A concrete tiny instance. Take variables $x_1, x_2, x_3$ and the 3-SAT formula

The table (a partial truth-table search, exactly what an NP verifier checks one row at a time given a certificate) shows $\varphi$ is satisfiable, witnessed by $(x_1,x_2,x_3) = (F,F,F)$ or $(T,T,F)$. Verifying either certificate costs $O(|\varphi|)$ time — three clause evaluations — matching the NP membership argument exactly. Finding such a certificate from scratch, by contrast, is exactly the exponential-looking search that NP-completeness says (modulo P vs NP) has no known polynomial shortcut in general.

Step 3 — Connecting back to Cook-Levin. If $\varphi$ above had instead been produced by the tableau construction for some machine $M$ on some input $x$ — i.e., $\varphi = \varphi_x$ — then the assignment $(F,F,F)$ satisfying $\varphi$ would correspond, cell by cell, to an actual accepting computation history of $M$ on $x$. The truth-table search over 8 rows above stands in, at a toy scale, for the truth-table search over the full $O(p(n)^2)$-variable tableau formula that the general theorem reasons about.

Modern SAT solvers, built on decades of engineering atop the worst-case-hard core identified by Cook-Levin, are industrial workhorses: hardware companies use them for formal verification of processor and circuit designs, checking equivalence and absence of bugs across billions of possible input states. Software analysis tools use SAT and its generalization SMT (satisfiability modulo theories) to find security vulnerabilities and prove program correctness. Package managers and dependency resolvers (in operating systems and language ecosystems) frequently reduce version-compatibility resolution to SAT instances and hand them to off-the-shelf solvers. More broadly, the entire discipline of proving problems intractable — used across operations research, cryptography, computational biology, and AI planning — rests on the reduction methodology that Cook-Levin made possible. Cryptographic hardness assumptions, scheduling software that instead uses heuristics and approximation once NP-hardness is established, and compiler optimizations that deliberately avoid provably-hard subproblems all trace their justification back to this single 1971 theorem. Understanding it is the gateway to Classic NP-Complete Problems, where the reduction technique is applied dozens of times over, and to Coping with NP-Hardness, which asks what to do in practice once a problem is confirmed to be in this class.

Ask the tutor: Can you show me, step by step, how the Cook-Levin tableau construction changes if the Turing machine has multiple tapes instead of one?