Course contentsShow
← Computer Science
Lesson 1916 of 2,87243. Complexity TheoryFree lesson

Cook-Levin Theorem

Understanding the proof that SAT is NP-complete, establishing the first known NP-complete problem.

Cook-Levin Theorem

You'll learn why the Cook-Levin Theorem is a landmark result that established the first NP-complete problem and opened the door to understanding computational hardness.

What Is the Cook-Levin Theorem?

The Cook-Levin Theorem (1971) proves that the Boolean Satisfiability Problem (SAT) is NP-complete. This means:

  1. SAT is in NP (you can verify a solution in polynomial time)
  2. Every problem in NP can be reduced to SAT in polynomial time

This was groundbreaking—it proved that if you could solve SAT efficiently, you could solve every NP problem efficiently!

The Core Idea of the Proof

The proof shows how to take any nondeterministic Turing machine (which defines an NP problem) and convert its computation into a Boolean formula.

Here's the recipe:

  1. Take an arbitrary NP problem with its verifier/nondeterministic TM
  2. Encode the machine's configuration (state, tape contents, head position) as Boolean variables
  3. Write formulas that say "if the machine is in configuration C₁, it can legally transition to configuration C₂"
  4. Add constraints that say "the machine starts in the initial state with input x"
  5. Add constraints that say "the machine eventually reaches an accepting state"

The resulting formula is satisfiable if and only if the original NP problem has a "yes" answer. This reduction works for any NP problem, proving SAT's universality.

Why This Matters

Think of SAT as a "universal translator" for computational problems. Every NP problem can be rephrased as a SAT instance. This makes SAT the foundational NP-complete problem—once it was discovered, thousands more were proven NP-complete simply by reducing them to SAT.

Key Takeaway: The Cook-Levin Theorem proves SAT is NP-complete by showing any NP problem can be polynomially reduced to checking if a Boolean formula (representing the computation) is satisfiable—making SAT the "hardest" problem in NP.