The P vs NP Problem
$1,000,000 USD
1971
Stephen Cook · Leonid Levin
Open
TL;DR
P vs NP asks one deceptively simple question: if a computer can verify a solution quickly, can it also find one quickly? "Quickly" here means in polynomial time — the size of the input matters, but tractably so. A sudoku puzzle is the classic intuition: given a filled grid, checking whether it's a valid solution takes a glance. But finding the solution from an empty grid, in the worst case, seems to require trying combinatorially many possibilities.
The class P contains problems solvable quickly. The class NP contains problems whose solutions can be verified quickly. Every P problem is trivially in NP (solving it is a way of verifying). The open question is the reverse: does NP ⊆ P? Almost every complexity theorist believes P ≠ NP, but nobody has proved it.
If P = NP, cryptography collapses (every RSA key becomes forgeable in polynomial time), protein folding becomes tractable, and mathematical theorem-proving is automated. If P ≠ NP, we get formal proof that certain problems are unavoidably hard, and modern cryptography stands on solid ground rather than "we haven't cracked it yet".
Formal statement
Is ? That is, for every decision problem whose solution can be verified in polynomial time by a deterministic Turing machine, does there exist an algorithm that solves it in polynomial time on a deterministic Turing machine?
Why it matters
P vs NP is the deepest question in computer science. Its resolution would either unlock a golden age of algorithmic breakthroughs (P = NP) or vindicate the entire foundation of modern cryptography, blockchain, and secure communication (P ≠ NP).
History
Stephen Cook introduced the concept of NP-completeness in his 1971 paper "The Complexity of Theorem-Proving Procedures," proving that Boolean satisfiability (SAT) is NP-complete — meaning every problem in NP can be reduced to SAT in polynomial time. Independently, Soviet mathematician Leonid Levin arrived at the same result around the same period. The pair of results is now called the Cook–Levin theorem.
Within a year, Richard Karp's 1972 paper "Reducibility Among Combinatorial Problems" showed 21 well-known problems were all NP-complete — vertex cover, Hamiltonian cycle, integer programming, and more. This exploded interest in the field. Suddenly, thousands of practical problems across biology, logistics, scheduling, and physics were revealed to be equivalent: solve any one in polynomial time and you solve them all.
The Clay Mathematics Institute listed P vs NP as one of its seven Millennium Prize Problems in 2000, with a $1,000,000 reward. Despite the attention, essentially no progress has been made on either direction.
Current status of research
A 2002 poll of complexity theorists showed 61% believed P ≠ NP. A 2019 update put that at 88%. But belief is not proof.
Known barriers rule out entire families of proof techniques:
- Relativization (Baker, Gill, Solovay, 1975): oracle proofs cannot resolve P vs NP.
- Natural proofs (Razborov, Rudich, 1994): a large class of "combinatorial" lower-bound proofs cannot work without breaking widely-believed cryptographic assumptions.
- Algebrization (Aaronson, Wigderson, 2008): a further barrier beyond relativization.
Any successful proof must sidestep all three barriers. This is why serious mathematicians consider P vs NP possibly the hardest open problem in mathematics — not because it's obscure, but because we don't even have candidate techniques.
Notable attempts
Dozens of proof announcements have circulated since 2000; none have survived peer review. Vinay Deolalikar's 2010 preprint claiming P ≠ NP briefly captured public attention before flaws were identified within weeks by the online mathematics community. The pattern is instructive: the problem attracts wave after wave of talented mathematicians whose attempts fail against known barriers.
What a resolution would mean
If P = NP with a small polynomial: modern cryptography (RSA, ECDSA, most blockchain security) collapses overnight. Optimization problems currently solved by heuristics get exact polynomial-time solutions. Automated theorem proving becomes feasible. Machine learning approaches change fundamentally.
If P ≠ NP: cryptography's foundations are formally secured. We know for certain that certain problems require exponential work in the worst case, and we can build systems on that certainty rather than empirical evidence.
Most likely outcome — a proof that P ≠ NP, decades from now, using a technique that doesn't exist yet.