P versus NP
If a solution can be checked quickly, can it also be found quickly? Open since 1971; a proof earns one million dollars.
Open in the interactive tree →The question is whether finding is as easy as checking. Most experts believe not (P is not NP), but nobody can prove it. Formulated by Cook in 1971, it became one of the seven Clay Millennium Problems in 2000, with a prize of one million US dollars.
As of October 2026
October 2026: still open, no accepted proof. The known barriers (relativization 1975, natural proofs 1994, algebrization 2008) rule out most known proof techniques. AI systems settle many side problems in 2026, but no workable approach to P versus NP itself is known, and the complexity theorist Lance Fortnow wrote in June 2026 that he does not expect a proof in his lifetime, by humans or machines.
What is missing
- A new proof technique that gets around relativization, natural proofs and algebrization at once
- Strong lower bounds: for an explicit problem, circuit lower bounds are still only slightly above 3n gates for n inputs, far from exponential
- A bridge between algebraic/geometric methods (geometric complexity theory) and combinatorics
- No sign that raw computing power helps: this is a proof problem, not a computation problem
Becomes possible once solved
- If P = NP: planning and optimization problems (logistics, chip design, protein folding) become efficiently solvable exactly
- If P is not NP: the first mathematically grounded limits on what computers can do
- Necessary groundwork for encryption with proven security
Open steps
- Explicit circuit lower bounds Medium AI leverageProve superlinear, ideally exponential, circuit-size lower bounds for an explicit function; for general circuits the best known is still only slightly above 3n gates.
- Technique beyond the three barriers Low AI leverageFind a proof method that avoids relativization, natural proofs and algebrization at once; no known approach does.
- Tighter hardness-of-approximation bounds High AI leverageImprove NP-hardness and average-case hardness bounds, where each step needs a concrete finite construction (a gadget or a special graph) that a verifier can check.
- Geometric complexity theory, computed Medium AI leverageConnect the algebraic obstructions of geometric complexity theory to combinatorial statements that can be computed and checked on small cases.
Where AI could help
Low AI leverage. A proof needs a new idea that beats known barriers; AI helps with finite gadget searches, not with that missing theory.
- Search finite combinatorial gadgets and extremal graphs that tighten hardness-of-approximation and average-case bounds
- Check side lemmas and formalize them in Lean
- Test candidate proof ideas against the known barriers and survey the literature
Shown so far
- In September 2025 Google researchers used AlphaEvolve to find new gadget constructions that tightened NP-hardness-of-approximation bounds for MAX-4-CUT (0.9883 to 0.987), according to the authors. source