qedbot

The Millennium Museum·Computational complexity

Open

P versus NP

If a solution to a problem can be checked quickly, can it also be found quickly?

Open. Three known barriers explain why standard techniques cannot settle it.

The exhibit

The problem, three ways

Curious

Checking a finished Sudoku is easy; solving one can be hard. P versus NP asks whether that gap is real: whether every problem whose answers are easy to check is also easy to solve. Most researchers believe not, and much of modern cryptography depends on it.

Undergraduate

P is the class of decision problems a deterministic Turing machine solves in polynomial time; NP is the class whose yes-instances have certificates checkable in polynomial time. Cook and Levin showed that Boolean satisfiability is NP-complete, so P equals NP if and only if satisfiability has a polynomial-time algorithm.

Specialist

Three barriers explain why familiar techniques fail: relativisation (Baker, Gill and Solovay), natural proofs (Razborov and Rudich) and algebrisation (Aaronson and Wigderson). Circuit lower bounds and geometric complexity theory remain the main programmes.

What would count

  • A proof that P differs from NP, or that they are equal, in the standard model of computation set out in Stephen Cook's Clay description.
  • Clay's conditions: publication in a qualifying outlet, two years, general acceptance, then a decision by its board.

Fidelity traps

  • Results in restricted models, such as monotone circuits or relativised worlds, are not the problem.
  • A formal proof must use the standard definitions of computation and polynomial time; a theorem about a simplified model proves nothing about P versus NP.

Who is attacking it

  • OpenAI: Says it began large-scale work on all the open Millennium problems on 1 September 2026. Source

The history

10 events
  1. 1950s
  2. 1956

    posed

    Gödel's letter

    In a letter to John von Neumann, Kurt Gödel asks, in effect, whether proofs can be found as quickly as they can be checked.

    Source

  3. 1970s
  4. 1971

    posed

    Cook's theorem

    Stephen Cook introduces NP-completeness and shows that Boolean satisfiability is NP-complete.

    Source

  5. 1972

    progress

    Karp's 21 problems

    Richard Karp shows that 21 natural combinatorial problems are NP-complete.

    Source

  6. 1973

    posed

    Levin

    Leonid Levin independently develops the theory of universal search problems in the Soviet Union.

    Source

  7. 1975

    barrier

    Relativisation

    Baker, Gill and Solovay show that techniques which relativise to oracles cannot settle the question.

    Source

  8. 1990s
  9. 1994

    barrier

    Natural proofs

    Razborov and Rudich show that a broad class of lower-bound arguments would break pseudorandom generators if it worked.

    Source

  10. 2000s
  11. 2000-05-24

    prize

    A Millennium Prize Problem

    The Clay Mathematics Institute names P versus NP one of seven problems carrying a $1,000,000 prize, with an official description by Stephen Cook.

    Source

  12. 2008

    barrier

    Algebrisation

    Aaronson and Wigderson identify a third barrier, extending relativisation to algebraic techniques.

    Source

  13. 2010s
  14. 2010

    dispute

    A claimed proof, withdrawn

    Vinay Deolalikar circulates a claimed proof that P differs from NP; experts quickly find fundamental gaps.

    Source

  15. 2026
  16. 2026-09-01

    AI

    OpenAI turns to the Millennium problems

    OpenAI says it began large-scale work on all the open Millennium problems.

    Source

  17. Next
  18. ?

    The next entry

    Follow this problem below to get an email the moment it moves.

Follow and discuss

All discussion

Discussion and bounties for this problem load here.