Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 59 · Complexity

NP-Completeness and the Cook-Levin Theorem

Define NP-hard and NP-complete, follow the idea behind the Cook-Levin theorem, then run a SAT brute-force and DPLL solver and a SAT to 3-SAT converter in Python.

Inside NP there is a special group of problems that are the hardest of all: if any one of them has a polynomial-time algorithm, every problem in NP has one. These are the NP-complete problems, and they are the reason the P versus NP question matters so much. Thousands of everyday problems, from scheduling to circuit design to protein folding, turn out to be NP-complete.

How could anyone prove that a problem is the hardest in a class with infinitely many members? Stephen Cook and Leonid Levin independently found the answer in 1971-1973. You pick one problem and show directly that every NP problem reduces to it. After that, hardness spreads through the cheap chain of reductions from the previous lesson.

NP-hard and NP-complete

A language B is:

  • NP-hard if A ≤p B for every A in NP. (B is at least as hard as everything in NP; B itself need not be in NP.)
  • NP-complete if B is NP-hard and B is in NP.
flowchart TD
    subgraph NPH["NP-hard"]
        subgraph NP["NP"]
            P["P"]
            C["NP-complete<br/>SAT, 3-SAT, CLIQUE, ..."]
        end
        H["Harder than NP<br/>e.g. halting problem"]
    end

Assuming P ≠ NP, the NP-complete problems lie in NP but outside P. NP-hard problems outside NP (such as the halting problem) are even harder.

The key consequence: if some NP-complete problem is in P, then P = NP. And if P ≠ NP, no NP-complete problem has a polynomial-time algorithm. NP-complete problems are the "most likely to be hard" members of NP, which is why finding an NP-complete problem is the standard sign that you should stop looking for a fast exact algorithm.

Boolean satisfiability

The anchor problem is SAT. A boolean formula is built from variables and the operators AND, OR and NOT. A formula is satisfiable if some assignment of true or false to its variables makes it evaluate to true.

TEXT
SAT = { <φ> : φ is a satisfiable boolean formula }

It is natural to restrict attention to conjunctive normal form (CNF): an AND of clauses, where each clause is an OR of literals (a variable or its negation). For example:

TEXT
(x1 ∨ ¬x2) ∧ (¬x1 ∨ x3) ∧ (x2 ∨ x3 ∨ ¬x1)

SAT is in NP: the certificate is a satisfying assignment, and evaluating the formula is polynomial. The question is how fast we can find the assignment. The obvious method tries all 2^n assignments. Smarter solvers, such as DPLL, propagate forced choices and backtrack, which helps enormously in practice but is still exponential in the worst case.

Python Brute force versus DPLL on SAT

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Cook-Levin theorem

Theorem (Cook-Levin). SAT is NP-complete.

We already know SAT is in NP. The hard direction is that every language A in NP reduces to SAT. Here is the idea of the proof, which is worth understanding even if you never write out the details.

Let A be in NP. Then some nondeterministic machine N decides A in time at most n^k. Given an input w of length n, we build in polynomial time a boolean formula φ that is satisfiable exactly when N has an accepting computation on w.

  1. Tableau. Draw the computation of N as a table with n^k rows (time steps) and n^k columns (tape cells). Each cell holds a symbol, or a symbol with a state attached where the head is. An accepting computation is a way to fill the table.
  2. Variables. For each cell (i, j) and each possible symbol s introduce a variable x[i,j,s], meaning "cell (i, j) holds s". There are polynomially many.
  3. Constraints. Write formulas that say: each cell holds exactly one symbol; the first row is the start configuration for w; some cell in the table holds the accept state; and every 2 by 3 window of the table is legal, meaning it follows from one of N's transition rules (this is where the nondeterminism sits, because a window may be legal in more than one way).
  4. Combine all constraints with AND. The size of φ is polynomial in n, and it can be written down in polynomial time.
flowchart TD
    I["Input w, machine N, bound n^k"] --> T["Tableau: n^k x n^k grid of cells"]
    T --> V["One variable per (cell, symbol)"]
    V --> F["φ = start ∧ moves ∧ accept"]
    F --> S["φ satisfiable ⇔ N accepts w"]

The tableau turns a computation into a formula. A satisfying assignment is an accepting computation written out cell by cell.

Because local legality of each 2 by 3 window guarantees that the whole table is a valid computation, a satisfying assignment exists iff there is an accepting branch. This single reduction works for every A in NP, so SAT is NP-hard.

From SAT to 3-SAT

SAT's formulas can be arbitrary. A friendlier anchor is 3-SAT: CNF formulas in which every clause has at most three literals (many textbooks say exactly three). It stays NP-complete, which makes it the usual starting point for further reductions. The conversion splits long clauses using fresh variables:

TEXT
(l1 ∨ l2 ∨ l3 ∨ l4 ∨ l5)  becomes
(l1 ∨ l2 ∨ y1) ∧ (¬y1 ∨ l3 ∨ y2) ∧ (¬y2 ∨ l4 ∨ l5)

The new formula is equisatisfiable: satisfiable exactly when the old one is, though not the same formula. If the original clause is true because some li is true, set the y variables to carry that truth along the chain. If every li is false, the chain forces a contradiction.

Python Converting CNF to 3-SAT and checking equisatisfiability

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of clauses grows by at most a constant factor plus the clause lengths, so the conversion is polynomial. Together with SAT being NP-complete, this proves 3-SAT is NP-complete. (Note that 2-SAT is in P, so the line between easy and hard falls exactly between clause size two and three.)

How to prove a new problem NP-complete

Once you have one NP-complete problem, the recipe never changes:

  1. Show the new problem B is in NP (give a certificate and a verifier).
  2. Pick a known NP-complete problem A and show A ≤p B.
  3. Conclude B is NP-complete.

The next lesson walks through this recipe on several classic problems.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. A language is NP-complete when it is

    NP-complete means two things: membership in NP, and every NP problem reduces to it (NP-hardness).
  2. 2. What does the Cook-Levin theorem state?

    Cook and Levin proved that SAT is NP-complete: every language in NP reduces to it in polynomial time.
  3. 3. In the tableau proof, which part of the formula encodes the machine's transition rules?

    Windows of the tableau are legal exactly when they follow from some transition. Local legality of every window makes the whole table a valid computation.
  4. 4. What is true of the formula produced by splitting clauses with fresh variables?

    Splitting clauses with fresh variables gives an equisatisfiable formula, which is all a reduction needs, and it adds variables.
  5. 5. If one NP-complete problem were solved in polynomial time, what would follow?

    Every NP problem reduces to the NP-complete one, so a polynomial algorithm for it would solve all of NP in polynomial time.

Summary

  • NP-hard means every NP problem reduces to it; NP-complete means NP-hard and in NP.
  • SAT is the first NP-complete problem (Cook-Levin), proved with a tableau that encodes an accepting computation as a formula.
  • 3-SAT stays NP-complete through equisatisfiable clause splitting; 2-SAT is in P.
  • Proving a new problem NP-complete: show it is in NP, then reduce a known NP-complete problem to it.
  • A polynomial algorithm for any NP-complete problem would give P = NP.

Next: Classic NP-Complete Problems