P vs NP: The Million-Dollar Problem at the Heart of Computer Science

A $1 Million Prize Has Gone Unclaimed Since 2000 — and May Stay That Way

The Clay Mathematics Institute designated seven problems as Millennium Prize Problems in 2000, each worth one million dollars to whoever proves or disproves them. Only one has been solved — the Poincaré Conjecture, proved by Grigori Perelman in 2003 (who declined the prize). P vs. NP remains open. It asks whether every problem whose solution can be quickly verified can also be quickly solved. If the answer is yes (P = NP), cryptography collapses, drug discovery accelerates, and optimization problems that consume millions of computing hours become trivial. If the answer is no (P ≠ NP) — the answer most experts expect — it formally establishes that certain problems are fundamentally, irreducibly hard. The question has been open since Stephen Cook formalized it in 1971.

Defining P and NP

The terminology refers to complexity classes — categories of problems grouped by the computational resources required to solve them.

Every problem in P is also in NP: if you can solve a problem quickly, you can certainly verify a solution quickly (just re-solve it). The open question is whether NP problems that seem to require exponential solving time might have undiscovered polynomial-time solutions.

Cook's Theorem (1971) and NP-Completeness

Stephen Cook, then at the University of Toronto, proved in his landmark 1971 paper "The Complexity of Theorem Proving Procedures" that the Boolean satisfiability problem (SAT) is NP-complete. This was the first NP-completeness proof. SAT asks: given a Boolean formula with n variables and AND/OR/NOT operations, does there exist an assignment of True/False values to the variables that makes the entire formula True?

• Cook proved that every NP problem can be transformed (reduced) to SAT in polynomial time
• If you found a polynomial-time algorithm for SAT, you could solve every NP problem in polynomial time — proving P = NP
• Richard Karp followed in 1972 with "Reducibility Among Combinatorial Problems," showing 21 other problems are all NP-complete, establishing the web of reductions connecting them
• Karp and Cook independently received the Turing Award (1982 and 1985, respectively), essentially the Nobel Prize of computer science

Why Verification Is Easier Than Solving

The intuitive gap between solving and verifying is central to the P vs. NP question. Consider a 1,000-piece jigsaw puzzle: assembling it from scratch may take hours. Verifying that a completed arrangement is correct takes seconds — just check that all edges match. Most NP problems have this structure. A Sudoku solution can be verified in linear time by checking rows, columns, and boxes. Finding the solution from scratch appears to require trying vastly more combinations.

For RSA cryptography, the verification gap is the security foundation: multiplying two 1,000-digit primes takes milliseconds (polynomial time). Finding those primes from their product — integer factorization — takes exponential time with the best known algorithms. If P = NP, RSA would be breakable.

Evidence That P ≠ NP

No proof exists, but substantial circumstantial evidence supports P ≠ NP:

• Over 10,000 papers have attempted to prove P = NP or P ≠ NP; none have succeeded despite effort by many of the world's best mathematicians and computer scientists
• Every NP-complete problem discovered since 1971 has resisted polynomial-time algorithms despite substantial practical motivation to find them
• A 2012 survey of complexity theorists by Gasarch found 83% believed P ≠ NP, 9% believed P = NP, and 8% had no opinion
• Natural proof barriers (Razborov-Rudich, 1994), relativization barriers (Baker-Gill-Solovay, 1975), and algebrization barriers (Aaronson-Wigderson, 2009) show that most known mathematical proof techniques cannot resolve the question — any proof must use fundamentally new methods

If P = NP: What Would Change

The consequences of P = NP would be immediate and sweeping across multiple fields.

The State of the Problem Today

Ryan Williams at Stanford proved in 2011 that NEXP (nondeterministic exponential time) is not contained in ACC0 (constant-depth circuits with modular counting gates) — the most significant circuit lower bound in decades. But this falls far short of resolving P vs. NP. Quantum computing offers a related but distinct consideration: quantum algorithms (like Shor's algorithm for factoring) can solve some NP problems more efficiently, but quantum computers do not collapse NP into P. The problem remains the central unsolved question in theoretical computer science, and there is no consensus on when — or whether — it will be resolved.