P vs NP | 3-SAT → Vertex Cover | Reduction | Cook-Levin Theorem
Graduate
§1 — Interactive Simulation
Ready — Press Play or Next to begin.
Speed:
0
Operations
0
Comparisons
0 / 0
Step
—
n
COMPLEXITY CLASSES:
P: solvable in poly time O(n^k)
NP: verifiable in poly time
NP-hard: at least as hard as all NP problems
NP-complete: NP ∩ NP-hard
REDUCTION A ≤_p B: solve A using B as subroutine
A poly-time reducible to B
If B in P then A in P
3-SAT ≤_p VERTEX-COVER (Cook-Levin, 1971):
Build gadgets for each variable and clause
k-vertex cover exists iff 3-SAT formula satisfiable
§2 — The Idea, Step by Step
Some puzzles are easy to check but seem nearly impossible to solve. Picture a giant jigsaw: if a friend hands you the finished picture you can confirm it's correct in a minute, yet building it from a heap of pieces might eat your whole weekend. NP-completeness is the mathematics of exactly that gap — the distance between checking an answer and finding one.
Sorting problems by difficulty. Computer scientists group problems by how the work grows as the input gets bigger. Call the input size $n$. The class P holds problems a computer can solve quickly, meaning the running time grows like a polynomial such as $n^2$ or $n^3$ — written $O(n^k)$. The class NP holds problems whose answer can be verified quickly: hand the computer a candidate solution (a "certificate") and it can check whether that certificate is valid in polynomial time. Solving is one way of checking, so every P problem is automatically an NP problem too: $P \subseteq NP$.
A worked example. Take a 9×9 Sudoku. To check a filled grid you scan 9 rows, 9 columns, and 9 boxes for duplicates — a fixed $27$ passes, fast no matter which puzzle you were handed. So Sudoku-checking sits comfortably in NP. Solving a blank grid, however, can force a search through an astronomical number of candidate fillings. Easy to check, painful to solve: that is the NP feeling in miniature.
The hardest problems in NP. A problem $B$ is NP-complete when two things hold: it is in NP, and every problem $A$ in NP can be rewritten as an instance of $B$ by a polynomial-time reduction, written $A \le_p B$. The reduction translates any instance of $A$ into one of $B$ so their yes/no answers always agree. The consequence is dramatic: a single polynomial-time algorithm for just one NP-complete problem would, through these reductions, crack all of NP at once — proving $P = NP$. The Cook–Levin theorem (1971) identified the first such problem, Boolean satisfiability (SAT); Karp then reduced SAT to 21 more, Vertex Cover among them, using the variable-and-clause gadgets shown in the derivation below. Whether $P = NP$ remains open — a Millennium Prize problem worth one million dollars — though almost everyone bets that $P \neq NP$.
Try this in the sim above. Slide $n$ from 4 up to 16 and watch the Step counter: each comparison is one cheap, easily-checked operation, which is what "verifiable" feels like. Notice the total Steps grow roughly like $n^2$, a polynomial — bump the input and the work grows manageably. That is life inside P. Now imagine the work instead grew like $2^n$, the brute-force cost of searching an NP-complete problem: at $n=16$ that is over $65{,}000$ units, versus the few hundred you see here. Picturing the counter at that scale is why we call these problems "intractable."
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average / amortized complexity
Φ(S)
Potential function of data structure state S
α(n)
Inverse Ackermann function (~constant)
Step 1 — P and NP. P = problems solvable in O(n^k) time. NP = problems where a given YES solution can be VERIFIED in O(n^k) time. Every problem in P is also in NP (just solve it, then verify). The P vs NP question: is there an NP problem that cannot be solved in polynomial time? Most believe P ≠ NP but this is unproven (Millennium Prize: $1M).
Step 2 — NP-Hardness via Reduction. Problem B is NP-hard if every problem A ∈ NP reduces to B in polynomial time (A ≤_p B). Meaning: if B has a polynomial-time algorithm, then so does every problem in NP — implying P=NP. Reduction shows B is 'at least as hard as' the hardest NP problems.
Step 3 — Cook-Levin Theorem (1971). 3-SAT is NP-complete (Cook 1971, independently Levin 1973). Given a Boolean formula in 3-CNF (3-literal clauses), is there a satisfying assignment? Any NP problem can be reduced to 3-SAT in polynomial time — proven by encoding a nondeterministic Turing machine's computation as clauses.
Step 4 — 3-SAT → Vertex Cover (sketch). For each variable x: create two nodes (x, ¬x) connected by an edge (variable gadget). For each clause (a ∨ b ∨ c): create a triangle (clause gadget) with one edge to each literal node. Set k = #variables + 2 * #clauses. Formula satisfiable ⇔ graph has k-vertex cover. Reduction is O(n) — so Vertex Cover is NP-complete.
Step 5 — The NP-Complete Zoo. Classic NP-complete problems: 3-SAT, Vertex Cover, Clique, Independent Set, Hamiltonian Cycle, TSP (decision), 3-Coloring, Subset Sum, Knapsack (decision), Bin Packing, Scheduling. All polynomially reducible to each other. Solving one in polynomial time solves all.
Step 6 — Coping with NP-Hardness. Exact: branch-and-bound, dynamic programming (exponential worst-case). Approximation: find solution within factor α of optimal in poly time (vertex cover: 2-approx greedy; TSP metric: 1.5-approx Christofides). Parameterized: FPT algorithms O(f(k) * n^c) for small parameter k. Heuristics: simulated annealing, genetic algorithms (no guarantee).
§4 — Frequently Asked Questions
What does it mean for a problem to be in NP? concept+
NP (nondeterministic polynomial) = problems where a YES answer has a certificate (witness) verifiable in polynomial time. Example: Hamiltonian Cycle — given a cycle, verify it visits all vertices in O(n). Finding the cycle may take exponential time, but checking one takes linear time.
If P = NP, what would change? concept+
All current public-key cryptography (RSA, ECC) would break — factoring integers is in NP. Drug discovery, protein folding, logistics would become polynomial. AI: learning optimal strategies would be easy. Most cryptographic protocols would be insecure. The mathematical proof system itself would change.
How do reductions work? concept+
A polynomial reduction from A to B transforms any instance of A into an instance of B in polynomial time, such that YES-instance of A ↔ YES-instance of B. If B is solvable in polynomial time: use the reduction + B's algorithm to solve A in polynomial time. So 'B is easy' implies 'A is easy'. Contrapositive: 'A is hard' implies 'B is hard'.
What is the difference between NP-hard and NP-complete? applied+
NP-complete: in NP AND NP-hard (hardest problems IN NP). NP-hard: at least as hard as NP-complete problems, but may NOT be in NP. Example: Halting Problem is NP-hard (undecidable!) but not in NP. TSP (optimization): NP-hard but not NP-complete (optimization, not decision problem).
Are there problems harder than NP-complete? nonobv+
Yes: PSPACE (solvable with polynomial SPACE, exponential time). PSPACE ⊃ NP (believed strictly). EXP: solvable in exponential time. NEXP: nondeterministic exponential. Undecidable: Halting Problem, Entscheidungsproblem — no algorithm exists, not even exponential.
What is a 2-approximation for Vertex Cover? deep+
Greedy: while edges remain: pick any edge (u,v), add BOTH u and v to cover, remove all adjacent edges. Result: at most 2×OPT vertices. Proof: each picked edge must have at least one endpoint in OPT, but we pick both endpoints — at most 2×OPT. No polynomial algorithm gives (2-ε)-approx unless P=NP (Khot-Regev 2008 assuming Unique Games Conjecture).
§5 — Misconceptions & Implementation Errors
Conceptual Misconceptions
✗ NP means 'not polynomial' (non-polynomial).
✓ NP stands for 'Nondeterministic Polynomial' — problems verifiable (not necessarily solvable) in polynomial time. The common misconception 'NP = hard' is wrong: every problem in P is also in NP.
✗ NP-complete problems cannot be solved efficiently.
✓ NP-complete problems have no KNOWN polynomial algorithm. It is not PROVEN they cannot be solved in polynomial time (P vs NP is open). There may exist a polynomial algorithm we haven't found yet.
✗ Showing a problem is in NP proves it is NP-hard.
✓ NP-hard means AT LEAST as hard as NP-complete. Showing a problem is in NP shows it is NOT harder than NP-complete. NP-hard requires showing a reduction FROM an NP-complete problem TO your problem.
Implementation Errors
✗ Forgetting to prove the reduction is polynomial-time.
✓ A reduction must run in polynomial time. An exponential reduction is useless — it wouldn't imply polynomial solvability. Always verify the reduction itself runs in O(n^k).
✗ Confusing the direction of reduction.
✓ To show B is NP-hard: reduce a KNOWN NP-hard problem A to B (A ≤_p B). The reduction goes FROM the known hard problem TO the new problem. Reducing B to A would only show A is at least as hard as B — the wrong direction.
✗ Assuming an approximation algorithm solves the NP-complete problem exactly.
✓ Approximation algorithms give solutions within a factor α of optimal — NOT the exact optimum. A 2-approximation for Vertex Cover may output a cover twice as large as minimum. Exact solution still requires exponential-time algorithms (unless P=NP).