Write and Explain Cook’s Theorem Cook–Levin Theorem | AI Research

Write and Explain Cook’s Theorem (Cook–Levin Theorem)

Verified Sources

Sep 29, 2026

Cook’s theorem (often grouped with the Cook–Levin theorem) is the foundational result in computational complexity that establishes SAT (Boolean satisfiability) as NP-complete. Concretely, it shows two things:

SAT is in NP (a satisfying assignment can be verified in polynomial time), and
Every language in NP can be reduced to SAT in polynomial time, meaning SAT is NP-hard, hence NP-complete. 2

A useful way to “write and explain” Cook’s theorem is to separate the story into (i) formal definitions (NP, reductions, NP-complete), (ii) the verifier-to-formula translation, and (iii) the resulting complexity consequence. We’ll follow that structure.

Key learning targets:

SAT
NP
NP-complete
Polynomial-time reduction
Cook reduction

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩
NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

Cook–Levin theorem / Cook’s theorem overview (NP-completeness of SAT)

Definitions you must write down before proving anything

To explain Cook’s theorem rigorously, you need standard definitions.

NP
A language $L$ is in NP if there exists a nondeterministic polynomial-time Turing machine deciding it, i.e., every input $x$ has an accepting computation of length polynomial in $|x|$ if and only if $x \in L$ .
Polynomial-time many-one reduction ( $\le_m^p$ )
We say $A \le_m^p B$ if there exists a polynomial-time computable function $f$ such that for all $x$ :

x \in A \iff f(x) \in B.

This is the type of reduction used in Cook’s theorem to show NP-hardness of SAT. 2

NP-complete
A language $B$ is NP-complete if:

$B \in \text{NP}$ , and
for every $A \in \text{NP}$ , $A \le_m^p B$ .
Cook’s theorem’s main goal is to show SAT meets both conditions. 2

NP (definition via nondeterministic polynomial time / verifiers). https://en.wikipedia.org/wiki/NP - Formal characterization of NP used in complexity proofs. ↩
NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩ ↩²
Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩
Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩

Write and prove Cook’s theorem (proof sketch with the core construction)

1
Step 1
Let $L \in \text{NP}$ . By definition, there exists a nondeterministic Turing machine $M$ and a polynomial $p(n)$ such that for any input $x$ with $|x|=n$ , $x \in L$ iff $M$ has an accepting computation that halts within $p(n)$ steps.

Footnotes

NP (definition via nondeterministic polynomial time / verifiers). https://en.wikipedia.org/wiki/NP - Formal characterization of NP used in complexity proofs. ↩
2
Step 2
Consider a time horizon $T=p(n)$ . Any accepting run can be viewed as a sequence of configurations $C_0, C_1, \dots, C_T$ (starting from the initial configuration and ending in an accepting one). The key idea is to encode the existence of such a sequence using Boolean variables. 2

Footnotes

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩
3
Step 3
Create variables that represent, for each time $t \in \{0,\dots,T\}$ and tape cell position $i$ , which tape symbol appears, and which state (if any) the head is in. Also include variables to represent head position / state. This forms a tableau encoding of the computation. 2

Footnotes

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩
4
Step 4
Write clauses ensuring (i) the initial configuration matches $x$ , (ii) transitions follow the transition function of $M$ , (iii) exactly one symbol/state assignment holds where required, and (iv) the final configuration is accepting. These constraints ensure the formula can be true only if the encoded computation is valid. 2

Footnotes

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩
5
Step 5
Prove both directions:
• If $x \in L$ , then the accepting run of $M$ gives a consistent tableau, producing a satisfying assignment for the constructed formula.
• If the formula is satisfiable, then the satisfying assignment defines a valid accepting computation of $M$ within $T$ steps, so $x \in L$ . 2

Footnotes

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩
6
Step 6
Show the constructed Boolean formula has size polynomial in $|x|$ (roughly because $T$ is polynomial and you add polynomially many local constraints). Since the mapping $f(x)=\varphi_x$ is computable in polynomial time, you get $L \le_m^p \text{SAT}$ . Together with $\text{SAT} \in \text{NP}$ , SAT is NP-complete. 3

Footnotes

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩

The heart of the explanation: “local constraints” simulate transitions

When you write the Cook theorem argument, the most important explanation sentence is usually:

“The Boolean formula enforces that consecutive configurations differ exactly according to the transition function of the nondeterministic machine, using local (time $t$ to $t+1$ ) constraints.”

This is why the tableau method works: TM computation is inherently “step-by-step,” and SAT can represent consistency across steps via clauses that constrain pairs of adjacent time layers. 2

A compact way to visualize the encoding is:

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩
Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩

Pro Tip: write Cook’s theorem as two proofs

To “write and explain” Cook’s theorem cleanly, structure it as: (1) SAT ∈ NP, (2) for arbitrary L ∈ NP, build a poly-time reduction L ≤p SAT via computation tableau. Readers follow faster when SAT’s membership and NP-hardness are separate mini-proofs. 2

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩
NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

Common pitfall: confusing NP with verification vs. search

NP is about existence of a short certificate verifiable in poly time (or equivalently nondeterministic poly-time computation), not about finding that certificate efficiently. Cook’s construction encodes existence of an accepting computation as satisfiability, not the act of finding it. 2

NP (definition via nondeterministic polynomial time / verifiers). https://en.wikipedia.org/wiki/NP - Formal characterization of NP used in complexity proofs. ↩
Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩

Why the theorem is “complete” for NP

Once you have shown that every NP language reduces to SAT, you can phrase Cook’s theorem as a completeness statement:

If you could solve SAT efficiently (e.g., in polynomial time), then by reduction you could solve every language in NP efficiently.
Conversely, if SAT is hard, then all of NP inherits that hardness under reductions.

Formally, Cook’s theorem implies SAT is NP-complete, meaning it is in NP and NP-hard. 2

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩
NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

From NP definitions to Cook’s theorem and NP-completeness

Define NP

Step A

NP languages have polynomial-size accepting witnesses (or nondeterministic poly-time machines). "

NP (definition via nondeterministic polynomial time / verifiers). https://en.wikipedia.org/wiki/NP - Formal characterization of NP used in complexity proofs. ↩

Define reductions

Step B

Polynomial-time many-one reductions preserve yes-instances. 2"

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩
Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩

Encode computation as SAT

Step C

Create tableau variables and clauses for valid transitions and acceptance. 2"

NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩
Reduction and NP-complete definitions via polynomial-time many-one reductions. https://en.wikipedia.org/wiki/NP-completeness - Explains reductions ( $\\le_m^p$ ) and the definition of NP-complete. ↩

Prove equivalence

Step D

Accepting run ↔ satisfiable formula; mapping is polynomial-time. 2"

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩
NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

Conclude NP-completeness

Step E

SAT ∈ NP and every NP language reduces to SAT. 2"

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩
NP-completeness (Cook–Levin theorem / Cook’s theorem) overview and SAT NP-completeness discussion. https://en.wikipedia.org/wiki/Cook%27s_theorem - States SAT is NP-complete and describes the core reduction idea. ↩

What Cook’s theorem establishes (and what each part requires)

Conceptual checklist for writing the proof.

Frequently needed details when you write the proof

Cook’s theorem: write/teach yourself terms

1 / 5

Question · Term

SAT

Click to reveal

Answer · Definition

Decision problem asking whether a Boolean formula has a satisfying assignment; SAT is the canonical NP-complete problem.

Stephen A. Cook, “The Complexity of Theorem-Proving Procedures” (1971). https://doi.org/10.1145/321694.321712 - Introduces Cook’s original NP-completeness result for SAT/related formulations. ↩

Input: x
Let M be the nondeterministic TM for L with runtime bound T=p(|x|)
Construct variables:
  - SymbolAt(t,i,s): symbol s at cell i at time t
  - StateAt(t,i,q): state q at cell i at time t (if head is there)
Add CNF clauses:
  - Initial configuration matches x
  - Exactly one symbol per cell per time
  - Exactly one head position/state per time
  - Local transition constraints from time t to t+1 according to M
  - At time T, some accepting state appears
Output: φ_x (the conjunction of all clauses)
Then: x ∈ L ⇔ φ_x ∈ SAT

Knowledge Check

Question 1 of 4

Q1Single choice

Cook’s theorem is commonly used to show that SAT is:

NP-complete

P-complete

co-NP-complete

PSPACE-complete

Explore Related Topics

Time Complexity via Divide-and-Conquer Recurrences (Two Worked Examples)

Write Short Notes on Armstrong's Axioms

Logic of the Pumping Lemma: Pigeonhole Principle, Iteration, and the Core Non-Role of Divide-and-Conquer/Recursion

Browse all research articles

Write and Explain Cook’s Theorem (Cook–Levin Theorem)

Footnotes

Cook–Levin theorem / Cook’s theorem overview (NP-completeness of SAT)

Definitions you must write down before proving anything

Footnotes

Write and prove Cook’s theorem (proof sketch with the core construction)

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

The heart of the explanation: “local constraints” simulate transitions

Footnotes

Pro Tip: write Cook’s theorem as two proofs

Footnotes

Common pitfall: confusing NP with verification vs. search

Footnotes

Why the theorem is “complete” for NP

Footnotes

From NP definitions to Cook’s theorem and NP-completeness

Define NP

Footnotes

Define reductions

Footnotes

Encode computation as SAT

Footnotes

Prove equivalence

Footnotes

Conclude NP-completeness

Footnotes

What Cook’s theorem establishes (and what each part requires)

Frequently needed details when you write the proof

Cook’s theorem: write/teach yourself terms

SAT

Footnotes

Knowledge Check

Explore Related Topics