NP-Completeness
Some problems have fast algorithms; others probably do not. NP-completeness is the formal language computer scientists use to talk about that "probably."
P and NP
Two complexity classes anchor the discussion:
- P is the set of problems solvable in polynomial time by a deterministic algorithm —
O(n),O(n log n),O(n³)are all in P. - NP is the set of problems whose solutions can be verified in polynomial time. Given a candidate answer, you can check it quickly, even if finding it might be slow.
Every problem in P is also in NP (verify by re-running the fast algorithm). The famous open question — does P = NP? — asks whether every quickly-verifiable problem also has a quickly-findable solution. Most computer scientists believe the answer is no.
NP-Complete and NP-Hard
A problem is NP-complete if it lies in NP and is at least as hard as every other problem in NP. If anyone ever finds a polynomial-time algorithm for a single NP-complete problem, every problem in NP becomes solvable in polynomial time. NP-hard problems are at least as hard as NP-complete ones, but might not lie in NP themselves.
Reductions
The way you prove a problem is NP-complete is by reducing a known NP-complete problem to it. If you can transform any instance of, say, SAT into an instance of your problem in polynomial time, then your problem must be at least as hard as SAT. Cook (1971) showed SAT is NP-complete; Karp (1972) reduced 21 classic problems to SAT. The list keeps growing.
Famous NP-Complete Problems
- SAT — given a Boolean formula, is there an assignment that makes it true?
- Traveling Salesman (decision form) — is there a tour visiting every city with cost at most k?
- Vertex cover, graph coloring, subset sum, knapsack (decision), Hamiltonian cycle
The example brute-forces a 4-city TSP. With 4 cities there are 3! = 6 tours; with 20 cities it is 19! ≈ 10^17 — feasible only with smarter approaches.
What to Do When You Hit One
Real NP-complete problems show up all the time. Your options:
- Approximation algorithms — find a provably-good (but not optimal) answer fast
- Heuristics — clever rules that work well in practice without strict guarantees
- Restricted inputs — many NP-hard problems become polynomial on trees or planar graphs
- Solvers — modern SAT and ILP solvers handle million-variable instances industrially
Try It Yourself
- Time the TSP brute force on 5, 6, 7, and 8 cities — watch the running time explode
- Implement a nearest-neighbor heuristic: always move to the closest unvisited city
- Pick a problem (course scheduling, sudoku, map coloring) and explain why it is NP-hard