The theory that lets you prove a problem is hard — not that you failed to find an algorithm, but that thousands of people have failed, and for a shared reason.
Chapter 1 mentioned NP-complete problems in passing. Chapter 34 makes the idea precise, and it is the most consequential piece of theory in the book. Its practical value is negative and enormous: it lets you stop looking. Proving a problem NP-complete means an efficient algorithm for it would give efficient algorithms for thousands of problems that have resisted fifty years of effort. That is not a proof of impossibility, but it is the strongest evidence available, and it redirects you from finding an exact fast algorithm to the alternatives in Chapter 35.
The theory is built on decision problems — those with a yes/no answer — rather than optimisation problems, because the machinery is cleaner.
k?” If the decision version is hard, the optimisation version is at least as hard, since an optimiser would answer the decision question immediately. Hardness results for decision problems therefore carry over.Formally a decision problem is a language: the set of binary strings encoding yes-instances. CLRS is careful about encodings, because a problem can change complexity if you encode it wastefully — the classic case being numbers written in unary rather than binary. A polynomial-time reduction between reasonable encodings preserves complexity, so any sensible encoding will do.
| Class | Definition | Intuition |
|---|---|---|
| P | Decidable in polynomial time | You can solve it fast |
| NP | Verifiable in polynomial time given a certificate | You can check a proposed answer fast |
| NP-hard | Every problem in NP reduces to it in polynomial time | At least as hard as everything in NP |
| NP-complete | In NP and NP-hard | The hardest problems in NP |
P ⊆ NP is obvious — if you can solve it fast you can verify it fast by ignoring the certificate and solving. Whether P = NP is the central open question in computer science, unresolved since 1971 and carrying a million-dollar Millennium Prize. Nearly everyone believes P ≠ NP, and nobody can prove it.NP is not “non-polynomial”. It stands for nondeterministic polynomial time, and the useful definition is about verification.
| Problem | Certificate for a yes-instance | Verification |
|---|---|---|
| Hamiltonian cycle | The cycle itself | Check it visits each vertex once and every step is an edge: O(V) |
| 3-CNF satisfiability | A satisfying assignment | Evaluate every clause: O(n) |
| Subset sum | The subset | Add it up: O(n) |
| Composite number | A non-trivial factor | One division |
NP = co-NP is another open question.L₁ is polynomial-time reducible to L₂, written L₁ ≤ᴵ L₂, if there is a polynomial-time computable function f such that for every input x: x ∈ L₁ if and only if f(x) ∈ L₂. Informally: L₂ is at least as hard as L₁, because a solver for L₂ plus the translation gives a solver for L₁.Lemma 34.3: If L₁ ≤ᴵ L₂ and L₂ ∈ P, then L₁ ∈ P.
Contrapositive: if L₁ is hard, then L₂ is hard too.Y is hard, reduce a known hard problem X to it: X ≤ᴵ Y. Reducing Y to something known hard proves nothing about Y. Mnemonic: reduce FROM a known-hard problem TO your problem. If you can turn any instance of a hard problem into an instance of yours, yours must be at least as hard.To show that problem Y is NP-complete:
1. Show Y ∈ NP.
Exhibit a certificate and a polynomial-time verifier. Usually easy.
2. Choose a known NP-complete problem X.
Pick one structurally similar to Y — this is where the skill is.
3. Construct a polynomial-time reduction f from X to Y.
Describe how to build an instance of Y from any instance of X.
4. Prove f is correct, in both directions:
x is a yes-instance of X ⇒ f(x) is a yes-instance of Y
f(x) is a yes-instance of Y ⇒ x is a yes-instance of X
5. Verify f runs in polynomial time.f(x) that do not encode solutions to x, is wrong.Every reduction needs a known-hard problem to start from. The first one had to be proved from the definition itself.
With one anchor established, everything else follows by chaining reductions:
X → Y is a proof that X ≤ᴵ Y, so Y inherits hardness from X.CLRS proves each link. Two worth remembering: CLIQUE ≤ᴵ VERTEX-COVER is almost trivial once you notice a clique in G is exactly an independent set in the complement of G; and HAM-CYCLE ≤ᴵ TSP is the simplest reduction in the chapter — give existing edges weight 0 and missing edges weight 1, then ask for a tour of total weight 0.
| NP-complete | In P — the near neighbour | The difference |
|---|---|---|
| Hamiltonian cycle: visit every vertex once | Euler tour: use every edge once | Vertices instead of edges |
| Longest simple path | Shortest path | One word |
| 3-CNF-SAT | 2-CNF-SAT | One literal per clause |
| 0-1 knapsack | Fractional knapsack | Whether items can be split |
| Graph 3-colouring | Graph 2-colouring (bipartiteness) | One colour |
| Vertex cover | Bipartite vertex cover | Restricting the graph class |
| Integer linear programming | Linear programming | Integrality |
| Subset sum, TSP, clique, set cover | — | — |
Proving your problem NP-complete is not the end of the engineering; it is the start of a different phase.
| Strategy | Give up on | Keep | Where |
|---|---|---|---|
| Approximation | Optimality | A proven bound on how far off you are | Chapter 35 |
| Special cases | Generality | Exactness on the inputs you actually get | e.g. trees, planar graphs, bounded width |
| Heuristics | Guarantees | Good behaviour on real data | Simulated annealing, genetic algorithms |
| Exponential but smart | Polynomial time | Exactness, with aggressive pruning | Branch-and-bound, SAT and ILP solvers |
| Parameterised | Polynomial in everything | f(k)·nO(1) for a small parameter k | Fixed-parameter tractability |
P ⊆ NP is clear; P = NP is open and almost universally believed false.Chapter 35, the last, takes the first of those strategies seriously. Approximation algorithms run in polynomial time and return a solution provably within a bounded factor of optimal — turning “this problem is hard” into “here is a solution, and here is exactly how far off it can be”.