P vs NP
The central open problem of computer science — and arguably of mathematics: is finding an answer fundamentally harder than checking one?
The problem in plain terms
P is the class of problems a computer can solve in polynomial time — time that grows reasonably with input size. NP is the class of problems whose proposed solutions can be checked in polynomial time. A filled Sudoku grid, a seating plan for quarrelsome guests, a truth assignment satisfying a logical formula: verifying any of them is quick, but finding them seems to require searching an exponential haystack. The question P = NP? asks whether that appearance is real: does efficient checkability imply efficient solvability? Everything turns on the NP-complete problems — the hardest in NP, each one encoding all the others. Crack any single one (SAT, traveling salesman, graph coloring…) in polynomial time and the whole class falls with it.
The two possible worlds. Nearly all experts bet on the left one — none can yet prove it.
History
- 1956 — Gödel's letter. In a private letter to the dying von Neumann, Gödel asks, in modern terms, whether proof-search can be done in polynomial time — noting that if so, “the mental work of a mathematician concerning yes-or-no questions could be completely replaced by a machine.” The letter was rediscovered only in 1988.
- 1965 — Complexity is born. Hartmanis and Stearns define computational complexity and time hierarchies; Edmonds identifies polynomial time with practical feasibility.
- 1971–73 — Cook, Levin, Karp. Stephen Cook proves SAT is NP-complete (Leonid Levin independently in the USSR); Richard Karp shows 21 classic problems are too. Suddenly hundreds of unrelated hard problems are revealed to be one problem in disguise.
- 1975 — The first barrier. Baker, Gill and Solovay show relativizing techniques — essentially all of classical computability — can never resolve P vs NP.
- 1994 — Natural proofs. Razborov and Rudich show the circuit lower-bound techniques of the 1980s are self-defeating: any “natural” proof of P ≠ NP would break the very cryptography that P ≠ NP underwrites.
- 2000 — The bounty. The Clay Mathematics Institute names P vs NP one of seven Millennium Prize Problems: one million dollars for a proof either way.
- 2008 — Algebrization. Aaronson and Wigderson erect the third barrier: even the algebraic tricks that cracked interactive proofs cannot settle the question.
- 2010 — The Deolalikar episode. A claimed proof of P ≠ NP triggers a remarkable open peer review online — and collapses within weeks. Over a hundred claimed proofs (both directions) have met the same fate.
- 2011 — A crack of light. Ryan Williams proves NEXP ⊄ ACC⁰ by turning faster algorithms into lower bounds — the “algorithmic method,” one of the few techniques that evades all three barriers.
Implications
If P = NP (constructively, with practical constants): public-key cryptography dies — along with the one-way functions behind signatures and blockchains. Optimization, scheduling, drug design and much of machine learning become exact rather than heuristic. Mathematics itself changes character: finding a proof becomes as easy as checking one, vindicating Gödel's automation of the mathematician. As Scott Aaronson put it, the gap between appreciating and creating would vanish — “everyone who could recognize a good investment strategy would be Warren Buffett.”
If P ≠ NP: the world stays as it looks — but we would finally know that search is irreducibly harder than verification: creativity, in this precise sense, cannot be automated away, and cryptography rests on real bedrock. Between the two poles, Russell Impagliazzo's five possible worlds map what is actually at stake:
Algorithmica — P = NP
Efficient algorithms exist for every problem whose answers can be checked efficiently. Optimization, learning and proof-search collapse into computation; most cryptography dies.
Heuristica — P ≠ NP, but easy on average
Hard instances exist but are freaks: real-world instances are tractable. Suspiciously close to the world SAT solvers already live in.
Pessiland — hard on average, no crypto
The worst world: typical instances are intractable, yet hardness cannot be harnessed into one-way functions. No fast algorithms and no cryptography either.
Minicrypt — one-way functions exist
Enough hardness for signatures and symmetric crypto, but not for public-key magic.
Cryptomania — public-key crypto exists
Hardness is structured enough for key exchange, RSA-style encryption and modern cryptography. Most researchers bet we live here — it is still only a bet.
Current state of affairs
- Still open — and the consensus is lopsided. In William Gasarch's recurring polls of complexity theorists, around 85–90% believe P ≠ NP. Almost nobody expects a resolution soon; many doubt it will come in their lifetime.
- The known techniques are provably insufficient. Three barriers — relativization, natural proofs, algebrization — together fence off essentially every tool that built 20th-century complexity theory. A proof needs genuinely new mathematics.
- Unconditional progress is humbling. After fifty years, the best general circuit lower bounds for SAT remain barely super-linear; the strongest concrete results (like Williams' NEXP ⊄ ACC⁰ and its descendants) live far from the frontier the question actually sits on.
- Two long-horizon programs carry the hopes. Mulmuley's Geometric Complexity Theory attacks the problem via algebraic geometry and representation theory on a self-declared multi-decade timescale; the algorithmic method keeps converting better algorithms into lower bounds.
- Meanwhile, practice mocks theory. Industrial SAT solvers routinely dispatch instances with millions of variables, and LLMs heuristically attack search problems — daily life increasingly resembles Heuristica, a world where worst-case hardness and average-case ease coexist. Quantum computing, for the record, is not expected to help: NP-complete problems are believed hard even for quantum machines.