Posed 1971 (Cook) & independently by Levin · Clay Millennium Prize (2000, $1,000,000) · the central question of computer science
How to read this page. A decision problem has a yes/no answer. P = problems a computer can solve in polynomial time (fast: time bounded by nk for input size n). NP = problems where a proposed "yes" answer can be checked in polynomial time, even if finding it seems hard. "Polynomial time" is the formal stand-in for "efficient." The question: is being able to check an answer quickly the same as being able to find one quickly?
0 · The claim, in one line
Is P = NP? That is: if a solution can always be verified fast, can it always be found fast? Almost everyone believes P ≠ NP (finding is genuinely harder than checking): but no one can prove it either way.
1 · The object: and why it is the whole ballgame
Checking is easy; searching is hard: that intuition is everywhere. Given a finished Sudoku, you verify it in seconds; solving a blank one feels exponentially worse. Given the factors of a number, you multiply to check; finding them underlies modern encryption. NP is the class of all such "easy-to-check" problems.
P ⊆ NP ⊆ PSPACE ⊆ EXPTIMEWe know P ≠ EXPTIME (the Time Hierarchy Theorem: some problems genuinely need exponential time). So the chain cannot all collapse. But we cannot prove the first inclusion P ⊆ NP is strict. That one gap is the million-dollar question.
If P = NP, the world breaks: every code based on "hard to reverse" falls (no secure encryption, because a cipher you can check is a cipher you can crack); but also every optimization (protein folding, logistics, theorem-proving, chip design) becomes tractable. The stakes are maximal in both directions.
2 · The fulcrum: NP-completeness
The reason this is one question and not thousands: the Cook–Levin theorem (1971) proved that a single problem, Boolean satisfiability (SAT), is NP-complete: every problem in NP can be efficiently re-encoded as a SAT instance. Karp (1972) then showed 21 famous problems are all NP-complete too; today the list is in the thousands.
If any one NP-complete problem is in P ⟹ all of NP is in P ⟹ P = NPThey are all the same problem in disguise. Crack one efficiently and the entire tower falls; prove one needs super-polynomial time and P ≠ NP.
SAT: is there a true/false assignment making a logic formula true?
Travelling Salesman (decision): a tour shorter than length L?
Clique, Graph Colouring, Hamiltonian Cycle, Subset-Sum, Knapsack: all NP-complete, all equivalent.
Two possible universes. Left: the believed world, where P (fast-solvable) sits strictly inside NP and the NP-complete problems are forever out of reach of fast algorithms. Right: the collapse, where finding equals checking and the whole hierarchy flattens. We cannot prove which universe we live in.
3 · Every connection: what hangs on the answer
Cryptography: P ≠ NP is a necessary condition for one-way functions (the basis of all public-key encryption). If P = NP, essentially all current cryptography is breakable.
The Polynomial Hierarchy: if P = NP, the entire hierarchy (PH) collapses to P: a cascade far beyond the single question.
Mathematics itself: if P = NP (with a practical algorithm), finding proofs becomes as easy as checking them: mathematical discovery would be partly automatable.
Expert belief: polls of complexity theorists (Gasarch, 2002/2012/2019) run ~85–90% for P ≠ NP: but belief is not proof, and a minority seriously entertain P = NP or independence.
4 · Every serious attack: and exactly how far each got
(a) Diagonalization
The technique that separates P from EXPTIME (the Time Hierarchy Theorem). Natural first weapon.
(b) Circuit lower bounds
Try to prove some NP problem needs super-polynomially many logic gates. Real wins on restricted circuits: constant-depth circuits can't compute parity (Furst–Saxe–Sipser; Håstad's switching lemma); monotone circuits for Clique need exponential size (Razborov, 1985).
(c) Geometric Complexity Theory (GCT)
Mulmuley & Sohoni's program recasts P vs NP (via the permanent-vs-determinant question) as a problem in algebraic geometry and representation theory: the most serious "new structure" attack.
5 · Why it breaks down: the honest crux
P vs NP is unusual: we can prove that whole families of techniques are incapable of settling it. Three "barrier theorems" have each executed a line of attack:
Barrier 1: Relativization (Baker–Gill–Solovay, 1975). Imagine giving every machine a free "oracle" that answers some fixed problem instantly. There exists an oracle A making PA = NPA, and another oracle B making PB ≠ NPB. Any proof technique that still works when an oracle is bolted on (and diagonalization does) cannot decide P vs NP: because the answer flips depending on the oracle. This killed diagonalization on day one.
Barrier 2: Natural Proofs (Razborov–Rudich, 1997). Almost every circuit lower bound works by finding a property that is "large" and "constructive": a natural property distinguishing hard functions from easy ones. Razborov and Rudich proved that any such natural property would itself be an efficient algorithm for breaking pseudorandom generators: i.e. it would refute the very cryptographic hardness almost everyone believes in. So if strong one-way functions exist (the same belief underlying P ≠ NP), natural proofs cannot prove P ≠ NP. The main weapon refutes its own premise.
Barrier 3: Algebrization (Aaronson–Wigderson, 2008). The one technique that beat relativization: arithmetization, which proved IP = PSPACE: was shown to still fail here. Extending oracles to their algebraic (polynomial) versions, the same flip-both-ways obstruction returns. So arithmetization-style proofs are out too.
Where that leaves the frontier. A valid proof must be non-relativizing, non-naturalizing, and non-algebrizing all at once. Essentially the only known result threading all three needles is Ryan Williams' NEXP ⊄ ACC⁰ (2011): a genuine breakthrough, but about a far larger class against a far weaker circuit model. It is astronomically short of what P vs NP needs. Concretely: we still cannot prove that any NP problem requires even circuits of more than roughly linear size. The true target is super-polynomial. The gap between what the barriers permit and what the problem demands has barely moved in 50 years: and GCT, the one program designed to evade the barriers, is by its own authors' estimate decades from maturity, with a 2016 result (Bürgisser et al.) ruling out the clean "occurrence obstructions" it had hoped to use.
The pattern. Unlike most open problems (where we lack ideas) P vs NP is a problem where we can prove our ideas are insufficient. Every general technique either flips under an oracle (Barrier 1/3) or would break cryptography if it worked (Barrier 2). That is why a field obsessed with this question for half a century has not moved the general lower bound past near-linear. The barriers don't just explain the lack of a proof: they explain the lack of progress.
6 · Status: confirmed
Unsolved No proof of P = NP or P ≠ NP exists. It is not even known to be independent of standard axioms. The belief P ≠ NP is near-universal but unproven.
What a genuine proof would require: either (i) a lower-bound method that provably evades all three barriers and is strong enough to show an NP-complete problem has no polynomial-size circuits (proving P ≠ NP): GCT is the leading candidate framework; or (ii) an actual polynomial-time algorithm for one NP-complete problem such as SAT (proving P = NP), which would shock the field and break cryptography. Faster SAT solvers, more NP-complete problems, or restricted-circuit bounds do not settle it.
Credit where it is due. Cook (1971) & Levin (independently, the NP-completeness of SAT); Karp (1972, the 21 problems); Baker, Gill & Solovay (1975, relativization); Furst–Saxe–Sipser & Håstad (constant-depth bounds); Razborov (1985, monotone bounds); Razborov & Rudich (1997, natural proofs); Aaronson & Wigderson (2008, algebrization); Mulmuley & Sohoni (GCT); Ryan Williams (2011, NEXP ⊄ ACC⁰); Bürgisser and collaborators (2016). The unsolved problem is claimed by no one here: if it is ever solved, that proof is offered freely to the world.