A ∈ NP ≤p SAT | Complexity Atlas

The construction

Let $A\in\mathrm{NP}$ and let $M$ be a nondeterministic machine deciding $A$ in polynomial time $q(n)$ . On input $x$ of length $n$ :

The tableau. Consider the $q(n)\times q(n)$ table $T_{M,x}$ : row $i$ encodes the configuration of $M$ after $i$ steps, as a single string in which the state is written immediately left of the scanned cell. The table is wide enough because in $q(n)$ steps the head cannot travel more than $q(n)$ cells.
The variables. For every cell $(i,j)$ and every symbol $s$ of the alphabet $L=\Gamma\cup Q\cup\{\#\}$ , introduce a Boolean variable $x_{i,j,s}$ meaning "cell $(i,j)$ holds symbol $s$ ".
The formula. $\varphi=\varphi_{cell}\wedge\varphi_{start}\wedge\varphi_{accept}\wedge\varphi_{move}$ $φ = φ_{ce l l} \land φ_{s t a r t} \land φ_{a cce pt} \land φ_{m o v e}$ :
- $\varphi_{cell}$ — every cell holds exactly one symbol;
- $\varphi_{start}$ — the first row is the initial configuration on $x$ ;
- $\varphi_{accept}$ — the accepting state appears somewhere in the table;
- $\varphi_{move}$ — every $2\times3$ window is legal, i.e. consistent with the transition function of $M$ .
Return $\langle\varphi\rangle$ .

The heart of the construction is $\varphi_{move}$ : global legality of a computation is enforced entirely by local checks. Two consecutive rows represent a legal step of $M$ iff every $2\times3$ window across them is legal — because a single step changes only the scanned cell and its neighbours.

Visualization

Input x = 10 · time bound T = 3 · tableau width S = 5

t=0

⊢

[q0,1]

0

□

Correctness — both directions

A ∈ NP ∈ ⟹ SAT ∈

Suppose $x\in A$ . Then $M$ has an accepting run on $x$ of length $\le q(n)$ . Fill the table according to exactly that run, and set $x_{i,j,s}=1$ iff cell $(i,j)$ of that table holds $s$ .

This assignment satisfies all four parts: $\varphi_{cell}$ because each cell holds one symbol; $\varphi_{start}$ because the first row was filled with the initial configuration; $\varphi_{accept}$ because the run accepts, so the accepting state occurs; $\varphi_{move}$ because consecutive rows describe a legal step of $M$ , hence every $2\times3$ window is legal. So $\varphi$ is satisfiable.

SAT ∈ ⟹ A ∈ NP ∈

Suppose $\varphi$ is satisfiable and let $\pi$ be a satisfying assignment. Read a table off it: since $\pi$ satisfies $\varphi_{cell}$ , every cell $(i,j)$ has exactly one symbol $s$ with $\pi(x_{i,j,s})=1$ , so the table is well defined.

Since $\pi$ satisfies $\varphi_{start}$ , the first row is the initial configuration on $x$ . Since it satisfies $\varphi_{move}$ , every $2\times3$ window is legal, so — by induction on rows — each row follows from its predecessor by a legal step of $M$ . That is, the table describes a genuine run of $M$ on $x$ . Since $\pi$ satisfies $\varphi_{accept}$ , that run reaches the accepting state. Hence $M$ has an accepting run on $x$ , so $x\in A$ .

Cost of the reduction

TimeO(q(n)^2) up to polylog factors

SpaceO(q(n)^2)

Output sizeO(q(n)^2 · |L| · log q(n)) bits

The tableau is $q(n)\times q(n)$ cells with $|L|$ variables each — $O(q(n)^2)$ variables — and $|L|$ is a constant fixed by $M$ , not by the input. $\varphi_{move}$ contributes one clause per window, and the number of windows is $(q(n)-1)\cdot(q(n)-2)=O(q(n)^2)$ ; the number of possible six-tuples per window is $|L|^6$ , again constant. So $|\varphi|=O(q(n)^2)$ up to constants and the $\log$ needed to encode indices — polynomial in the input size, which is all that is required.

What it buys

$\mathrm{SAT}$ is NP-complete. It is the first problem whose hardness was proved from scratch — every other reduction in the course leans on it through the transitivity of $\le_p$ .

Pitfalls

The reduction builds the formula from $\langle M\rangle$ and $x$ alone. It does not run $M$ and does not know whether an accepting run exists — the filled table appears only in the correctness proof, where assuming "an accepting run exists" is legitimate.
The bound $q(n)$ limits the number of steps, and therefore the width too — the head cannot travel further than the number of steps it took. Without that bound the table would not be polynomial and the whole construction would collapse.

The chain

Used later by

Where this was read from

Lesson 9משפט 1: משפט קוק–לוין
Guided exercisecook-levin-tableau
2025 '1 מועד 1The size of the tableau $T_{M,x}$ and how many variables it generates.
2024 '3 מועד 2Reading a sub-circuit out of the output of the Cook–Levin reduction in its CIRCUIT-SAT form.