Math Foundations · math·4 · step 4 of the spine · layer II

Tractability: P vs NP and reductions

est 20h · logged 0h · started — · touched —

Of the problems we can solve in principle, which can we solve before the heat death of the universe? The "what happens when N doubles" lens, P as solving and NP as verifying (and why it's called NP), decision vs optimization, Turing vs Karp reductions, Cook-Levin and Karp's 21 problems, what engineers actually do with NP-hard problems, and the hook to BQP — why a quantum computer is not a parallel brute-forcer.

Context

Turing asked what can be computed at all, given unlimited time. Cook, Levin, and Karp (1971–72) asked the question that governs practice: what can be computed before the heat death of the universe? The lens that makes it stick: when the input doubles, what happens to the work? Polynomial growth stays on Earth; exponential growth crosses a wall — at 2^N, adding one item doubles everything, and hardware can't save you. NP does not mean "not polynomial": it means verifiable in polynomial time, and P vs NP asks whether easy checking implies easy finding — the same asymmetry as checking a proof versus discovering one. Cook-Levin showed SAT is universal (every NP problem compiles into it); Karp's 21 reductions showed the pattern is everywhere. Still open, with a million-dollar bounty and — if answered "yes" — consequences for cryptography, optimization, and the nature of creativity itself.

How to read it

Anchor. Moore & Mertens, The Nature of Computation, chapters 4–6 — the complexity core, split out from the limits of computation so it gets the attention it deserves. Do a few reductions by hand; they're the unit's real content.

Companion. Aaronson, Quantum Computing Since Democritus, chapters 6–7 — complexity classes with attitude, and the honest version of what quantum computers can and cannot speed up (Grover is quadratic; NP ⊄ BQP is the expectation).

Companion. Fortnow, "The Status of the P versus NP Problem" (CACM, free) — the field's own summary of where things stand.

Optional. Fortnow, The Golden Ticket — the popular narrative; Sipser chapter 7 for theorem-proof rigor.

The habit to build: whenever anyone says a problem is "hard," ask which kind — undecidable, exponential, or just unsolved?

next action

done when you can

Give the N→2N growth factor for O(1), O(log N), O(N), O(N log N), O(N²), O(2^N), O(N!).Define NP without using the word "hard", and explain why P ⊆ NP.Perform one Karp reduction by hand (3-SAT to Clique or Vertex Cover).Explain how a yes/no decision oracle yields the optimal value via binary search.Say why Grover's quadratic speedup does not make NP-complete problems easy.Connect to Gödel: finding a proof vs checking one is the same asymmetry as solving vs verifying.

resources

●The Nature of Computation— Cristopher Moore & Stephan Mertensanchor · book
●Quantum Computing Since Democritus— Scott Aaronsoncompanion · book
○The Status of the P versus NP Problem— Lance Fortnowcompanion · paper
○The Golden Ticket: P, NP, and the Search for the Impossible— Lance Fortnowoptional · book
○Introduction to the Theory of Computation— Michael Sipseroptional · book

sessions

unlocks Unit 7 (Aaronson assumes exactly this complexity literacy). Unit 3 of the Information page (resource-bounded Kolmogorov complexity).