NP-Completeness

P, NP, and the verifier's-eye view

Complexity theory sorts decision problems — yes/no questions — by the resources needed to answer them. P is the class of decision problems solvable in polynomial time by a deterministic algorithm. NP (nondeterministic polynomial time) is the class of problems whose yes-answers are verifiable in polynomial time: if the answer is yes, there exists a short certificate (a witness) that a deterministic verifier can check in time polynomial in the input length.

Sudoku is the canonical intuition pump. Solving a blank 9×9 grid from scratch is hard; but hand me a filled grid and I can verify in a glance that every row, column, and box contains 1–9 exactly once. The filled grid is the certificate; the row/column/box check is the polynomial-time verifier. Every problem in NP has this shape — hard to find, easy to check. And P ⊆ NP trivially: if you can solve in polynomial time, you can ignore the certificate and re-solve to verify.

The billion-dollar question is whether that containment is strict. Does P = NP — is every efficiently-checkable problem also efficiently-solvable? It is one of the seven Clay Millennium Prize problems, and the overwhelming consensus is P ≠ NP, though no proof exists either way.

NP-hard, NP-complete, and the reduction backbone

NP-completeness is defined through polynomial-time reductions. We write A ≤ₚ B ("A reduces to B") if there is a polynomial-time function f mapping instances of A to instances of B such that x is a yes-instance of A if and only if f(x) is a yes-instance of B. Intuitively, B is at least as hard as A: any solver for B, plus the cheap translation f, solves A.

• NP-hard: a problem B is NP-hard if every problem A in NP satisfies A ≤ₚ B. B is at least as hard as everything in NP. Crucially, B itself need not be in NP — it need not even be a decision problem. The halting problem is NP-hard (it's undecidable, so certainly no easier), and the optimization version of TSP is NP-hard without being in NP.
• NP-complete: a problem is NP-complete if it is NP-hard and in NP. It is the hardest problem that is still "fair" — its yes-answers are verifiable, and everything in NP funnels down to it.

Reductions are transitive: if A ≤ₚ B and B ≤ₚ C, then A ≤ₚ C (compose the two polynomial maps; polynomial-of-polynomial is polynomial). This transitivity is the engine of the whole field: once one problem is proven NP-complete from first principles, every subsequent proof just reduces from an already-known NP-complete problem.

The Cook-Levin theorem — bootstrapping the first one

There is a chicken-and-egg problem. To prove B NP-complete by reduction, you need a known NP-complete problem to reduce from. Where does the first one come from? Stephen Cook answered this in 1971 (Leonid Levin proved it independently in the USSR), and the Cook-Levin theorem is the foundation stone: Boolean satisfiability (SAT) is NP-complete.

SAT asks: given a Boolean formula over variables with AND, OR, NOT, is there an assignment of true/false to the variables that makes the whole formula true? SAT is obviously in NP — the satisfying assignment is the certificate, and evaluating the formula on it is linear. The hard direction is NP-hardness: showing every NP problem reduces to SAT.

Cook's insight is a generic reduction. Any problem L in NP is decided by some nondeterministic Turing machine M that runs in polynomial time p(n). Cook encodes the entire tableau of M's computation — the state of the tape, head position, and machine state at every one of the p(n) time steps — as Boolean variables, and writes clauses enforcing that (1) the first row is the input, (2) each row follows from the previous by M's transition rules, and (3) some row is accepting. The resulting formula, polynomial in size, is satisfiable exactly when M has an accepting computation on the input. That formula is the reduction from L to SAT. Because L was an arbitrary NP problem, SAT is NP-hard, hence NP-complete.

Karp's 21 problems — the explosion

Cook gave the world one NP-complete problem. In 1972, Richard Karp's paper "Reducibility Among Combinatorial Problems" gave it 21, showing that a startling variety of well-known problems are all secretly the same difficulty. Karp built a reduction tree rooted at SAT: SAT → 3-SAT → CLIQUE → VERTEX COVER → HAMILTONIAN CIRCUIT, and so on, branching out to graph coloring, subset-sum, partition, set cover, and Steiner trees. Each arrow is a polynomial-time reduction.

The cultural impact was enormous. Karp demonstrated that NP-completeness was not a quirk of one artificial problem but a deep property cutting across scheduling, graph theory, logic, and number theory. Today the catalog runs to thousands of NP-complete problems (Garey and Johnson's 1979 book Computers and Intractability is the classic reference), and finding a new problem is NP-complete is a routine — if often clever — exercise in constructing the right reduction. Cook, and later Karp, both received the Turing Award for this line of work.

A worked reduction: 3-SAT ≤ₚ Independent Set

To see how a reduction actually works, here is the classic one from 3-SAT (SAT where every clause has exactly three literals) to Independent Set (given a graph and a number k, is there a set of k vertices with no edge between any two?).

Given a 3-SAT formula with m clauses, build a graph as follows:

• Gadget per clause: for each clause, create a triangle of three vertices, one per literal. The triangle's internal edges force us to pick at most one literal from each clause.
• Conflict edges: connect any two vertices in different triangles that hold contradictory literals — one labelled x and the other ¬x. This forbids choosing a literal and its negation simultaneously.
• Ask for k = m: an independent set of size m must take exactly one vertex from each triangle (they're mutually adjacent), and the conflict edges guarantee the chosen literals are consistent.

An independent set of size m exists if and only if there is a consistent choice of one true literal per clause — i.e., a satisfying assignment. The construction is clearly polynomial: 3m vertices and at most O(m²) edges. Since 3-SAT is NP-complete and Independent Set is in NP (the vertex set is the certificate), Independent Set is NP-complete. From here, VERTEX COVER (its complement) and CLIQUE (independent set in the complement graph) fall in one more line each.

The single most common mistake: reduction direction

The direction of a reduction is the part everyone gets backwards at first. To prove your problem X is NP-hard, you reduce a known NP-complete problem K to X: K ≤ₚ X. You are showing "X is at least as hard as K." Reducing the other way — X ≤ₚ K — proves nothing about X's hardness; it only shows X is no harder than K, which is what being in NP already gives you.

To prove X is NP-COMPLETE:

  Step 1 — X ∈ NP
    Give a certificate c and a verifier V such that
    V(instance, c) runs in poly time and accepts
    iff instance is a YES-instance.

  Step 2 — X is NP-HARD
    Pick a KNOWN NP-complete problem  K   (usually 3-SAT).
    Build a poly-time map  f : instances(K) -> instances(X)
    such that:
        k is YES for K   <=>   f(k) is YES for X.
    Direction:  K  --f-->  X      (reduce FROM known hard problem)

  Conclusion:
    X in NP  AND  X NP-hard   =>   X is NP-complete.

A correct reduction must satisfy three things: f runs in polynomial time, yes-instances map to yes-instances, and — the half people forget — no-instances map to no-instances (equivalently, the "if and only if" holds in both directions).

NP-hard vs NP-complete vs P — at a glance

	P	NP	NP-complete	NP-hard
Solvable in poly time?	Yes	Unknown (open)	Only if P = NP	Only if P = NP
Verifiable in poly time?	Yes	Yes (by definition)	Yes	Not necessarily
In NP?	Yes	Yes	Yes	Not necessarily
Every NP problem reduces to it?	No (unless P=NP)	No	Yes	Yes
Must be a decision problem?	Yes	Yes	Yes	No (can be optimization)
Example	2-SAT, shortest path	Factoring, graph iso	3-SAT, CLIQUE, TSP-decision	Halting problem, TSP-optimization

The famous NP-complete problems

• 3-SAT. Satisfiability with three literals per clause. The universal "source" for reductions because its clause structure is easy to encode into gadgets. 2-SAT, by contrast, is in P (linear time via strongly connected components).
• CLIQUE. Does a graph contain a complete subgraph on k vertices? Reduces from 3-SAT; verifying a claimed clique is trivially polynomial.
• VERTEX COVER. Is there a set of k vertices touching every edge? The exact complement of Independent Set (a set S is a vertex cover iff its complement is an independent set), so both are NP-complete together.
• Traveling Salesman (decision). Given cities, distances, and a budget B, is there a tour visiting all cities of total length ≤ B? The decision form is NP-complete; the optimization form ("find the shortest tour") is NP-hard.
• HAMILTONIAN CYCLE / PATH. Does a graph have a cycle visiting every vertex exactly once? Contrast with the Eulerian cycle (every edge once), which is in P — a tiny change in wording flips the complexity.
• SUBSET SUM / PARTITION / KNAPSACK (0-1 decision). Number-theoretic members of Karp's list, weakly NP-complete — they admit pseudo-polynomial dynamic programming that is polynomial in the numeric values but exponential in the number of bits.
• GRAPH COLORING (chromatic number ≥ 3). Can a graph be colored with k colors so no edge is monochromatic? 2-coloring is in P (bipartiteness check); 3-coloring is NP-complete — another sharp 2-vs-3 boundary.

Common misconceptions and pitfalls

• "NP means non-polynomial." No — NP stands for nondeterministic polynomial time. Every problem in P is also in NP. NP is about verifiability, not about being slow.
• "NP-complete means impossible to solve." They are all decidable and solvable by exhaustive search; only the worst-case polynomial-time guarantee is missing. Modern SAT solvers routinely dispatch industrial instances with millions of variables.
• "NP-complete = NP-hard." NP-complete is the strictly smaller intersection of NP-hard and NP. The halting problem is NP-hard but not NP-complete because it isn't in NP (it isn't even decidable).
• Reducing in the wrong direction. To prove your problem hard, reduce a known-hard problem to it, not the reverse (see above).
• Confusing weak and strong NP-completeness. Subset-Sum has a pseudo-polynomial DP; it's weakly NP-complete. 3-SAT and CLIQUE are strongly NP-complete — hard even when all numbers are written in unary — so no pseudo-polynomial algorithm exists unless P = NP.

What to do when your problem is NP-complete

• Approximation algorithms. For optimization variants, settle for provably-near-optimal. Vertex Cover has a simple 2-approximation; metric TSP has Christofides' 1.5-approximation.
• Exact solvers. SAT solvers (DPLL/CDCL), integer linear programming, and constraint solvers exploit structure to crush real-world instances despite the exponential worst case.
• Fixed-parameter tractability. Vertex Cover is solvable in O(2ᵏ · n) — exponential only in the parameter k, not the input size, so small covers are found fast.
• Heuristics and metaheuristics. Simulated annealing, genetic algorithms, and local search find good-enough solutions without guarantees when correctness can be sacrificed for speed.
• Restrict the input. Many hard problems become polynomial on trees, planar graphs, or bounded-treewidth instances — check whether your real inputs live in a tractable subclass.