NP-Completeness & Cook-Levin

Polynomial-time reductions, NP-hardness, and why SAT is NP-complete.

The idea

NP-completeness identifies the hardest problems in $\mathsf{NP}$: the languages to which every other language in the class reduces.

The comparison is made by a polynomial-time mapping reduction. Writing $A \le_{\mathrm{P}} B$ means there is a function $f$, computable in polynomial time, with $w \in A$ if and only if $f(w) \in B$. It is the mapping reduction of computability theory with a time bound attached, and it makes precise the claim that $B$ is at least as hard as $A$, up to polynomial overhead.

A language $B$ is NP-hard when every $A \in \mathsf{NP}$ satisfies $A \le_{\mathrm{P}} B$, and NP-complete when it is NP-hard and itself lies in $\mathsf{NP}$. An NP-complete language concentrates the difficulty of the whole class: a polynomial-time algorithm for it would give one for every language in $\mathsf{NP}$, so $\mathsf{P} = \mathsf{NP}$; and if $\mathsf{P} \neq \mathsf{NP}$, then no NP-complete language lies in $\mathsf{P}$.

Theorem (Cook-Levin theorem).

$\mathrm{SAT}$, the set of satisfiable Boolean formulas, is NP-complete.

The first NP-completeness proof is the hard one, because NP-hardness quantifies over every language in $\mathsf{NP}$ at once. Every proof after the first is easier: reduce a language already known to be NP-complete to the new one, since reductions compose.

Ways to work on it

• Walkthrough. Learn how reductions order problems by hardness and what makes a problem NP-complete.
• Practice. Work out which way reductions transfer hardness and how they compose.
• Hardest. Chain reductions to prove a problem NP-complete and bound the size of the Cook-Levin construction.

Not sure where to start? Take the ten-question placement test.