NP-Completeness

Verification, polynomial reductions, and what makes a problem NP-complete.

The idea

NP-completeness is the theory of which problems we can reasonably hope to solve efficiently. It is stated for decision problems, whose answer is yes or no; little is lost, since finding a smallest vertex cover and deciding whether one of size $k$ exists are efficiently interconvertible.

P is the class of decision problems solvable in polynomial time. NP is the class of decision problems whose yes-instances have a certificate: evidence that a polynomial-time checker can verify, such as a satisfying assignment for a satisfiable formula, or the cover itself for a graph with a small vertex cover. NP concerns checking a proposed answer, not producing one, and every problem in P is in NP.

Problems are compared by polynomial-time reduction. A reduction from $A$ to $B$ converts any instance of $A$, in polynomial time, into an instance of $B$ with the same answer. It carries algorithms forward — convert, then run $B s algorithm — and therefore carries hardness backward: $B$ is at least as hard as $A$.

Definition (NP-complete).

A decision problem $X$ is NP-complete when $X$ is in NP and every problem in NP reduces to $X$ in polynomial time.

Thousands of natural problems are NP-complete, and each is a hardest problem in NP: a polynomial-time algorithm for any one of them would yield one for all of NP at once and settle whether P $=$ NP. Decades of failure to find such an algorithm are the evidence that none exists.

Ways to work on it

• Walkthrough. NP as verification, vertex cover, and polynomial-time reductions.
• Practice. Validate a certificate for an NP problem.
• Hardest. The Independent Set / Vertex Cover reduction and its hardness consequence.

Builds on

• Dynamic Programming

Leads to

• Approximation Algorithms

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