What you'll learn
Not every problem has a fast algorithm — and for a huge, important class, nobody knows whether one exists. This module is the theory of intractability: the classes P and NP, the million-dollar P vs NP question, and what NP-completeness means for the problems you'll meet.
By the end you'll be able to:
- Define P and NP via decision problems
- Explain reductions and NP-completeness
- Recognize famous NP-complete problems and respond appropriately
P: efficiently solvable
We frame these questions with decision problems — those with a yes/no answer ("Is there a route shorter than 100?"). The class P is the problems solvable in polynomial time — O(nᵏ) for some constant k. Everything in this course so far — sorting, shortest paths, matching — lives in P. We treat polynomial as the boundary of "efficient."
NP: efficiently checkable
NP is the problems whose yes-answers can be verified in polynomial time given a certificate (a proposed solution). You may not know how to find a Hamiltonian cycle quickly, but if someone hands you one, you can check it in linear time. Every problem in P is in NP (if you can solve it fast, you can check it fast), so P ⊆ NP:
NP — verifiable in polynomial time
P — solvable in polynomial time
sorting, shortest paths, matching…
NP-complete — the hardest in NP
SAT, TSP (decision), clique, 3-coloring…
If any NP-complete problem is in P, then P = NP and the whole picture collapses.
The P vs NP question
Is checking really easier than solving — or is P = NP? This is the most famous open problem in computer science (and a $1,000,000 Clay Millennium Prize). Almost everyone believes P ≠ NP: that some problems are genuinely hard to solve even though solutions are easy to verify. But no one has proved it.
Reductions & completeness
A reduction transforms problem A into problem B in polynomial time, so that solving B solves A (written A ≤ₚ B). It means B is "at least as hard as" A. A problem is NP-complete if it's in NP and every NP problem reduces to it — the very hardest problems in NP. The Cook-Levin theorem proved SAT (boolean satisfiability) is NP-complete; thousands of problems were then shown NP-complete by reducing from it.
Key idea
Famous NP-complete problems
- SAT / 3-SAT — satisfy a boolean formula.
- Travelling salesman (decision) — a tour under a given length.
- Clique / independent set / vertex cover — dense or sparse vertex subsets.
- Graph coloring — color with
kcolors so no edge is monochromatic. - Subset sum / knapsack (decision) — hit an exact target.
- Hamiltonian cycle — visit every vertex exactly once.
Note
P = NP. That's why recognizing one matters — it tells you the whole family is out of easy reach.Recap & quick check
Key takeaways
- P = decision problems solvable in polynomial time; NP = solutions verifiable in polynomial time.
- P ⊆ NP; whether P = NP is the famous open question (most believe P ≠ NP).
- A reduction A ≤ₚ B shows B is at least as hard as A.
- NP-complete = in NP and every NP problem reduces to it (SAT was the first, via Cook-Levin).
- Recognizing an NP-complete problem tells you to switch to approximation or heuristics.
Quick check
1. What defines the class NP?
2. What does it mean that a problem is NP-complete?
3. A polynomial reduction A ≤ₚ B tells you:
4. Which was the first problem proven NP-complete (Cook-Levin)?
If a problem is intractable, you don't give up — you approximate. And we'll wrap the whole course together. Next up: Module 36 — Coping with Hard Problems & Choosing an Algorithm.