← Problem set
MILLENNIUMComputational complexity · posed 1971
P versus NP
If a solution can be checked quickly, can it also be found quickly? Almost everyone believes no; nobody can prove it.
Formal statement
Obstruction
Why the direct approaches fail
Three proof barriers stand in the way, and every known technique runs into at least one. Relativization (Baker–Gill–Solovay) kills diagonalization. Natural proofs (Razborov–Rudich) kill combinatorial circuit lower bounds, conditional on strong one-way functions. Algebrization (Aaronson–Wigderson) kills the arithmetization methods that survived the first two.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Produce a lower-bound technique that provably evades all three barriers simultaneously.
- 02Improve the best known circuit lower bound for an explicit NP function beyond 5n − o(n).
- 03Formalize the geometric complexity theory program’s representation-theoretic obstruction hypothesis.
- 04Establish a new separation between uniform and non-uniform models that transfers to P/NP.
Under attack now
P vs NP has its own lane in the solver, running continuously alongside every other problem.