Coursify

Write and Explain Cook’s Theorem (Cook–Levin Theorem) — A Complete Learning Section

Write and Explain Cook’s Theorem (Cook–Levin Theorem) — A Complete Learning Section

Verified Sources
Sep 29, 2026

Cook’s theorem—often grouped with the Cook–Levin theorem—states that the Boolean satisfiability problem is NP-complete. In a standard form:

  • SAT
  • NP

Cook proved that SAT is in NP and that every language in NP can be reduced to SAT in polynomial time, establishing NP-completeness.2

A common way to “explain” the theorem (without skipping the math) is:

  1. Take an arbitrary language L∈NPL \in \text{NP}.
  2. Model its membership using a nondeterministic polynomial-time verifier.
  3. Encode the existence of an accepting computation as a Boolean formula.
  4. Show the formula is satisfiable iff the verifier accepts.
  5. Conclude SAT is NP-hard; combined with SAT ∈\in NP, SAT is NP-complete.2

Key concepts used throughout:

  • NP-complete
  • Cook reduction
  • Certificate
  • Reduction

Footnotes

  1. Stephen A. Cook, “The Complexity of Theorem-Proving Procedures,” Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971). https://dl.acm.org/doi/10.1145/800157.801047 - Original SAT NP-completeness result. ↩ ↩2

  2. Wikipedia, “Boolean satisfiability problem.” https://en.wikipedia.org/wiki/Boolean_satisfiability_problem - SAT is NP-complete; common references to Cook’s theorem. ↩

  3. Wikipedia, “Cook's theorem (computer science).” https://en.wikipedia.org/wiki/Cook%27s_theorem - Statement and explanation of NP-completeness framework. ↩

Cook–Levin (Cook’s) Theorem: SAT is NP-complete (Intuition to Proof)

Formal setup: what “write and explain Cook’s theorem” means

1) Decision problems and reductions

To prove a problem is NP-complete, we show:

  • (i) Membership in NP: the problem can be verified in polynomial time.
  • (ii) NP-hardness: every problem in NP reduces to it by a polynomial-time many-one reduction.

Cook’s theorem is commonly summarized as:

  • SAT is NP-complete.2

2) The verifier view of NP

For any L∈NPL \in \text{NP}, there exists a polynomial-time verifier VV such that:

  • x∈Lx \in L iff there exists a certificate ww with V(x,w)V(x,w) accepting within polynomial time.

Cook’s proof works (at a high level) by translating the existence of an accepting computation of such a verifier into a Boolean satisfiability instance.2

Footnotes

  1. Wikipedia, “Boolean satisfiability problem.” https://en.wikipedia.org/wiki/Boolean_satisfiability_problem - SAT is NP-complete; common references to Cook’s theorem. ↩

  2. Wikipedia, “Cook's theorem (computer science).” https://en.wikipedia.org/wiki/Cook%27s_theorem - Statement and explanation of NP-completeness framework. ↩ ↩2

  3. Stephen A. Cook, “The Complexity of Theorem-Proving Procedures,” Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971). https://dl.acm.org/doi/10.1145/800157.801047 - Original SAT NP-completeness result. ↩

Cook’s theorem construction: from an NP verifier to a SAT instance

  1. 1
    Step 1

    Let L∈NPL \in \text{NP}. Choose a nondeterministic (or equivalent verifier) machine MM that decides LL in polynomial time.

  2. 2
    Step 2

    If MM runs in time p(n)p(n), then any computation on input xx has at most T=p(∣x∣)T=p(|x|) steps, so the “computation tableau” has polynomial size.

  3. 3
    Step 3

    Create variables representing what MM is doing at each time step: tape symbol, head position, and control state at each t∈{0,…,T}t \in \{0,\dots,T\}.

  4. 4
    Step 4

    Encode that at time t=0t=0, the tape contains the input xx in the correct format and the head starts in the initial position with the start state.

  5. 5
    Step 5

    For each step t→t+1t \to t+1, add clauses that ensure the chosen state/head/symbol at time t+1t+1 follows from the transition rules of MM.

  6. 6
    Step 6

    Add “consistency” clauses: at each time tt, exactly one machine state is active, the head is at exactly one position, and the tape symbols match the variables.

  7. 7
    Step 7

    Include clauses forcing that at some time t≤Tt \le T the accepting state is reached (or equivalently, the final configuration satisfies acceptance).

  8. 8
    Step 8

    Let φ\varphi be the conjunction of all tableau clauses. Its size is polynomial in ∣x∣|x|.

  9. 9
    Step 9

    If x∈Lx \in L, there exists an accepting computation; setting tableau variables according to that computation satisfies φ\varphi. Conversely, a satisfying assignment defines a valid accepting computation.

  10. 10
    Step 10

    The mapping x↦φx \mapsto \varphi is computable in polynomial time and preserves the yes/no answer, so L≤pSATL \le_p \text{SAT}.

Why the construction works (the “explain” part)

Cook’s central idea is: a SAT instance can express the existence of a valid computation history.

Tableau encoding intuition

Think of a nondeterministic computation as a sequence of configurations. The proof encodes the entire history into a grid/tableau:

  • Columns: time steps tt
  • Rows: tape cells (or head/tape components)
  • Variables: what symbols/states appear at each location in the tableau

Then:

  • Constraints ensure local consistency: each step obeys the machine’s transition function.
  • If the constraints all hold globally, the tableau spells out a complete accepting run.2

From NP-hardness to NP-completeness

Once we show every L∈NPL \in \text{NP} reduces to SAT, SAT is NP-hard. Since SAT is also in NP (a satisfying assignment is a certificate that can be checked in polynomial time), SAT becomes NP-complete.2

Footnotes

  1. Stephen A. Cook, “The Complexity of Theorem-Proving Procedures,” Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971). https://dl.acm.org/doi/10.1145/800157.801047 - Original SAT NP-completeness result. ↩

  2. Wikipedia, “Cook's theorem (computer science).” https://en.wikipedia.org/wiki/Cook%27s_theorem - Statement and explanation of NP-completeness framework. ↩ ↩2

  3. Wikipedia, “Boolean satisfiability problem.” https://en.wikipedia.org/wiki/Boolean_satisfiability_problem - SAT is NP-complete; common references to Cook’s theorem. ↩

type="tip" title="Pro Tip" content="When explaining Cook’s theorem, focus on the iff proof: satisfiable formula ↔ valid accepting computation history. Most confusion comes from skipping the correctness argument."

type="warning" title="Common pitfall" content="Don’t claim Cook’s theorem uses an “efficient algorithm to find satisfying assignments.” NP-completeness is about decision problems and reductions, not about tractability of finding solutions."

Relationship to variants (SAT, 3-SAT, and Levin)

Many courses next ask why we can replace SAT by restricted forms like 3-SAT. The typical story is:

  1. SAT is NP-complete (Cook).
  2. There are standard polynomial reductions from SAT to 3-SAT, preserving satisfiability.
  3. Therefore 3-SAT is NP-complete.

This is part of the “NP-completeness ecosystem” that emerged after Cook’s original theorem and subsequent refinements.2

Footnotes

  1. Wikipedia, “Boolean satisfiability problem.” https://en.wikipedia.org/wiki/Boolean_satisfiability_problem - SAT is NP-complete; common references to Cook’s theorem. ↩

  2. Wikipedia, “Cook's theorem (computer science).” https://en.wikipedia.org/wiki/Cook%27s_theorem - Statement and explanation of NP-completeness framework. ↩

Cook’s theorem proof structure (high-level checklist)

What you must establish to claim NP-completeness.

Historical/Conceptual Roadmap

Define NP via certificates

NP verifier view

Membership can be verified in polynomial time for some witness."

Reduce any NP problem to SAT

Cook reduction framework

Construct a formula that represents an accepting computation."

Encode computation history as logic

Tableau + constraints

Local transition constraints imply global validity."

Combine SAT ∈ NP with NP-hardness

NP-completeness conclusion

SAT is NP-complete under polynomial-time reductions."

Frequently asked explanation details

Cook’s theorem — self-check deck

1 / 5
Question · Term

What does it mean for SAT to be NP-complete?

Click to reveal
Answer · Definition

SAT is in NP and is NP-hard: every problem in NP reduces to SAT via a polynomial-time reduction.

1 φ = (InitialConditions) ∧ (TransitionConstraints over all t) ∧ (TapeConsistency) ∧ (AcceptanceConstraint) 2 3- AcceptanceConstraint typically enforces that an accepting state appears in the tableau.

Knowledge Check

Question 1 of 4
Q1Single choice

Which two properties are required to prove SAT is NP-complete?

Explore Related Topics

1

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

2

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

3

Rice’s Theorem (Undecidability of All Nontrivial Semantic Properties)

Browse all research articles