NP-Completeness

6 min read#computation

The hardest problems in NP, all interreducible — solve one efficiently and you solve them all.

Contents

NP-Completeness

An NP-complete problem is one of the hardest problems in NP, in a precise sense: it is in NP, and every other problem in NP can be transformed into it by an efficient (polynomial-time) reduction. These problems are the keystones of P versus NP. Find a fast algorithm for one of them and you have, automatically, a fast algorithm for all of NP — proving P = NP. Prove that one of them needs exponential time and you have proved P ≠ NP. They stand or fall together.

There are thousands of them, scattered across logic, scheduling, graph theory, number theory, and games — yet underneath they are, computationally, the same problem wearing different costumes.

Reduction: the universal translator

The magic ingredient is the polynomial-time reduction. To reduce problem A to problem B is to write an efficient translator that turns any instance of A into an instance of B with the same yes/no answer. If such a translator exists, then "B is easy" implies "A is easy" — just translate and solve.

A graph you can watch: 3-coloring

A classic NP-complete problem: can the vertices of a Graph be painted with just three colors so that no edge joins two same-colored vertices? Checking a proposed coloring is trivial — glance at every edge. Finding one means searching a space of 3^V colorings. The sketch below hunts for a valid 3-coloring of a wheel graph by trial: red edges are conflicts (endpoints clash); it keeps trying until every edge is satisfied, then locks in green.

Searching for a 3-coloring of a wheel graph. Each pass recolors the vertices; edges with matching endpoints flash red as conflicts. When a conflict-free coloring is stumbled upon, the whole graph confirms green — easy to verify, hard to find.

Other faces of the same beast include the clique problem (is there a set of k mutually connected vertices?), the traveling salesman decision problem, and SAT itself. A polynomial reduction connects every one of them to all the others.

So what do we do about them?

Since (almost certainly) no fast exact algorithm exists, real systems sidestep the wall: approximation algorithms that get provably close, heuristics like Simulated Annealing and Genetic Algorithms that find good-enough answers, or solvers tuned for the easy instances that arise in practice. NP-completeness does not mean "give up" — it means "stop looking for a perfect, fast, general method, because by P versus NP it probably cannot exist."

A problem is shown to be NP-complete. What does this tell you?

See also

Related topics

  • P versus NPThe open question of whether every problem whose solution is easy to check is also easy to solve.
  • Complexity ClassA grouping of problems by the computational resources — time or memory — needed to solve them.
  • Big-O NotationA way to describe how an algorithm's cost grows with input size, keeping only the dominant term and ignoring constants.
  • GraphA set of nodes joined by edges — the minimal mathematical object for describing relationships of any kind.
  • Computability & ComplexityWhat a machine can compute in principle, and how much time and space it takes in practice — from the Turing machine to the million-dollar P versus NP question.
  • Genetic AlgorithmOptimize with no gradient at all — keep a population of candidate solutions, let the fittest reproduce with mutation and crossover, and watch quality climb.

Referenced by