Symptom

Three weeks into a project, you are still trying to write an exact algorithm.

The problem is yours and it looks specific: assign delivery vans to routes such that every stop is covered, no van exceeds its capacity, and the total distance is minimized. Nothing in the literature matches it exactly. So you keep going — better data structures, smarter pruning, a cleverer greedy pass with a repair step — and each version works on your test set and falls over on production data.

Nobody told you the search was hopeless, because from the inside it never looks hopeless. Each failure suggests a specific fix. What you needed on day two was the ability to look at the problem and say: that is set cover with a knapsack constraint, that is NP-hard, exact-and-fast is not available, and the real question is which of exactness, speed, or generality I am giving up.

Karp’s paper is where the profession acquired that ability.

Statement

Twenty-one natural combinatorial problems are NP-complete. Karp gave polynomial-time reductions from SAT to each, arranging them in a tree so that each reduction starts from a problem proved complete earlier on the page.

The list is the founding catalogue: satisfiability, 0-1 integer programming, clique, set packing, vertex cover, set covering, feedback node set, feedback arc set, directed and undirected Hamiltonian circuit, 3-SAT, chromatic number, clique cover, exact cover, hitting set, Steiner tree, 3-dimensional matching, knapsack, job sequencing, partition, and max cut.

The content is not any single one of them. It is that these twenty-one — drawn from logic, graph theory, scheduling, number theory, and operations research, studied for decades by communities that did not talk to each other — are all the same problem wearing different clothes. Solve any one in polynomial time and you solve all of them, plus everything else in NP.

The catalogue has since grown past several thousand problems. Garey and Johnson’s 1979 book listed roughly three hundred and is still the standard reference.

Argument

Cook–Levin (T027) supplies the first complete problem. Everything after that is transitivity: if $A \le_p B$ and $B$ is NP-hard, then $B$’s hardness transfers to anything $B$ reduces to. So the work is entirely in exhibiting reductions, and the technique is worth seeing in miniature.

3-SAT $\le_p$ Independent Set. Given a 3-CNF formula with $m$ clauses, build a graph: one vertex per literal occurrence, so $3m$ vertices. Connect the three vertices within each clause into a triangle, and connect every vertex to every vertex holding its negation. Ask for an independent set of size $m$.

A triangle admits at most one vertex from each clause, so an independent set of size $m$ picks exactly one literal per clause. The negation edges guarantee it never picks both $x$ and $\neg x$. So an independent set of size $m$ is exactly a choice of one true literal per clause with no contradictions — a satisfying assignment. Conversely, any satisfying assignment gives such a set. The graph is built in linear time.

That is the whole shape: encode the choices as vertices, the constraints as edges, and let the target problem’s objective do the counting.

Independent Set $\le_p$ Vertex Cover. $S$ is independent exactly when its complement is a vertex cover, because an edge with both endpoints outside the cover would be an edge inside $S$. So ask for a cover of size $n - k$. The reduction is a subtraction — the same problem, read from the other side.

Vertex Cover $\le_p$ Set Cover. Elements are edges, and each vertex contributes the set of edges it touches. Covering all elements is covering all edges. A change of vocabulary, nothing more.

3-SAT $\le_p$ Hamiltonian Circuit is where the gadgets get real: each variable becomes a long two-way “highway” traversable left-to-right or right-to-left (true or false), each clause becomes a node that can be visited from any of its three literals’ highways, and a Hamiltonian circuit exists exactly when every clause node can be picked up by some true literal. Nobody guesses this in an afternoon, which is precisely why the catalogue is valuable: somebody already did it.

Why a tree rather than twenty-one proofs from SAT. Reducing knapsack from SAT directly would be brutal; reducing it from partition-flavoured problems is easy. The structure of Karp’s paper is the argument — a well-chosen intermediate makes the next reduction short, and building the catalogue in dependency order is what keeps each step checkable by eye.

The practical skill this buys. Once you have seen fifteen of these, you stop proving and start recognizing. “Choose one from each group, subject to pairwise conflicts” is 3-SAT or graph colouring. “Cover everything using fewest sets” is set cover. “Pack items under a budget” is knapsack. Your van-routing problem contains an exact cover and therefore will not have an exact fast algorithm, and you know this in ten minutes rather than three weeks.

Forbids

A polynomial exact algorithm for any of the twenty-one, unless P = NP. Including the ones that look easy. Partition — split a multiset into two equal halves — has a two-line statement and is NP-complete.

The assumption that a small change makes a problem tractable. 2-SAT is in P but 3-SAT is complete; 2-colouring is in P but 3-colouring is complete; shortest path is in P but longest path is complete. The tractability boundary sits between neighbours, so “mine is only slightly different” is not evidence.

Any claimed general fast solver for one of these. Such a claim is a claim of P = NP, and gets evaluated at that price.

The hope that unfamiliarity means unexplored. Your specific problem is almost certainly a known one with a gadget wrapped around it. Searching the catalogue is faster than searching for an algorithm.

Does not forbid

It does not stop production systems from solving these daily, at scale. Concorde has solved TSP instances with tens of thousands of cities to proven optimality, including an 85,900-city instance in 2006. CPLEX and Gurobi solve integer programs — Karp’s second problem — with millions of variables across logistics and airline scheduling. NP-hardness is a worst-case statement about an infinite family, and your instances are drawn from a structured distribution that branch-and-cut exploits.

It does not mean approximation is hopeless. Vertex cover has a trivial 2-approximation (take both endpoints of a maximal matching). Knapsack has an FPTAS: any accuracy you like, in time polynomial in $1/\epsilon$. Set cover has a $\ln n$-approximation from the greedy algorithm. That is T032’s subject, and the approximability landscape is wildly uneven across a list of problems that are all equivalent for exact solution.

It does not mean every instance is hard, or even that hard instances are common. Graph colouring is NP-complete, but register allocation in LLVM and GCC colours interference graphs constantly with a linear-scan or Chaitin-style heuristic, and real interference graphs are chordal or nearly so. The theorem describes the worst adversarial input, and your compiler is not facing an adversary.

It does not mean the parameters do not matter. Vertex cover is NP-complete but solvable in $O(1.28^k + kn)$ time for cover size $k$, which is fast whenever $k$ is small even if $n$ is enormous. “NP-hard” flattens a distinction that parameterized complexity (T033) restores, and it is the single most useful refinement of the theorem for practitioners.

It does not say your problem is hard just because it resembles one on the list. Hardness transfers along reductions in one direction only. Matching is in P even though it looks like set packing; 2-SAT is in P even though it looks like 3-SAT; min-cut is in P even though max-cut is complete. You have to actually check which side you are on, and the pairs that straddle the line are the ones worth memorizing.

Boundary

  • What the catalogue is really for. Not for proving things. For recognizing them. The value is a trained eye, which is why reading the reductions beats reading the list.
  • The min-cut/max-cut asymmetry. Minimizing a cut is polynomial; maximizing it is complete. Same object, opposite direction, opposite complexity. This is the single best cure for the intuition that structurally similar problems have similar difficulty.
  • Weak versus strong NP-hardness. Knapsack has a pseudo-polynomial $O(nW)$ dynamic program, which is fine when weights are small integers and exponential in the input’s bit length. TSP is strongly NP-hard and has no such escape. The distinction tells you whether “small numbers” is a usable restriction.
  • Special structures that collapse hardness. Many of the twenty-one become polynomial on trees, on bounded-treewidth graphs, on planar graphs (often via a PTAS), or on interval graphs. Checking whether your instances have structure is usually more productive than checking whether your heuristic can be tuned.
  • Optimization versus decision. Karp’s problems are decision problems, but self-reducibility means a decision oracle gives you the optimum by binary search plus fixing choices one at a time. That equivalence is why nobody worries about the distinction in practice.