Among the problems in NP some are special: if just one of them had a polynomial algorithm, then every problem in NP would have one. These are the NP-complete problems. Their existence is far from obvious, and the Cook-Levin theorem proves it by exhibiting the first example: the Boolean satisfiability problem, SAT. From there, a chain of reductions has shown that a great many practical problems are NP-complete.
Polynomial-time reductions
The key notion is a "cost-bounded" version of the mapping reduction. A is polynomial-time reducible to B, written A ≤ₚ B, if there is a function f computable in polynomial time such that:
w ∈ A if and only if f(w) ∈ B
The fundamental property: if A ≤ₚ B and B ∈ P, then A ∈ P. Just compute f(w), which has polynomial length, and run the algorithm for B. A composition of polynomials is a polynomial.
The definitions
- A problem B is NP-hard if A ≤ₚ B for every A in NP.
- A problem B is NP-complete if it is NP-hard and belongs to NP.
An NP-hard problem may lie outside NP: the halting problem, for instance, is NP-hard but not even decidable.
A direct consequence of the definitions:
if an NP-complete problem is in P, then P = NP.
This is why NP-completeness is regarded as strong evidence that no polynomial algorithm exists.
The SAT problem
A Boolean formula uses variables x₁, …, xₙ, the operators AND (∧), OR (∨), NOT (¬) and parentheses. It is satisfiable if some assignment of true/false values to the variables makes it true.
SAT = {⟨φ⟩ : φ is a satisfiable Boolean formula}
SAT is in NP: the certificate is the assignment, and evaluating the formula takes linear time.
The Cook-Levin theorem
SAT is NP-complete.
Since SAT is in NP, it remains to show that every problem A in NP reduces in polynomial time to SAT. We do not know A: we only know there is a nondeterministic machine N deciding it in time nᵏ. The reduction must work for any N.
The tableau idea
Fix an instance w of length n. Every computation branch of N on w can be represented as a tableau of size nᵏ × nᵏ:
- each row is a configuration of N;
- the first row is the initial configuration with input w;
- each row follows from the previous one by a transition of N;
- some row contains the accept state.
A tableau obeying these rules is an accepting tableau. N accepts w if and only if an accepting tableau exists. The reduction builds a formula φ that is satisfiable exactly when such a tableau exists.
The variables
For each cell (i, j) of the tableau and each symbol s that may appear (tape symbols and states), create a variable xᵢ,ⱼ,ₛ, which will be true when cell (i, j) contains s. There are O(n²ᵏ) variables, a polynomial number.
The four parts of the formula
The formula is the conjunction φ = φ_cell ∧ φ_start ∧ φ_move ∧ φ_accept.
- φ_cell: each cell contains exactly one symbol. For each cell we require that at least one variable is true and that no two are true together.
- φ_start: the first row encodes the initial configuration, with the start state and the input w followed by blanks.
- φ_accept: the accept state appears in some cell.
- φ_move: each row follows legally from the previous one.
The most interesting part is φ_move. The trick is to observe that a transition changes only the cells near the head. So it is enough to check every 2 × 3 window, that is blocks of three adjacent cells in a row and the three cells beneath them. A window is legal if it is consistent with the transition function. One proves that if the first row is correct and every window is legal, each row is a configuration following from the one before.
The number of possible legal windows depends only on N, not on n: it is a constant. For each position we write a disjunction over the legal windows, and the total size of φ_move stays polynomial.
The cost of the reduction
The formula φ has size O(n²ᵏ) and is written in polynomial time, simply by listing the constraints. Hence A ≤ₚ SAT for every A in NP.
From SAT to other problems
Once one NP-complete problem is known, proving that a new problem B is NP-complete takes only two steps:
- show that B is in NP, by exhibiting a verifiable certificate;
- reduce a known NP-complete problem to B in polynomial time.
By transitivity of reductions, every problem in NP then reduces to B. The first link in the chain is usually 3-SAT, the version of SAT where the formula is a conjunction of clauses with exactly three literals each. It is NP-complete too, and its regular structure makes it easy to transform into graphs, numbers or tables.
In short
- A ≤ₚ B means there is a polynomial transformation that preserves the answer.
- An NP-complete problem is in NP and every NP problem reduces to it; if one were in P, then P = NP.
- The Cook-Levin theorem shows SAT is NP-complete by encoding a machine's computation tableau in a formula.
- 2 × 3 windows check the legality of moves with a constant number of cases.
- For later problems it is enough to reduce from a known NP-complete problem, usually 3-SAT.
