Open problem, Applied and computational mathematics, Foundations of mathematics, posed 1971
P versus NP
Let P be the class of decision problems solvable by a deterministic algorithm in time polynomial in the input size, and let NP be the class of decision problems whose proposed solutions can be verified in polynomial time. The question is whether P = NP: does every efficiently verifiable problem admit an efficient algorithm to solve it?
As of 2026, P versus NP remains open, and most computer scientists conjecture P ≠ NP. Decades of research have identified formal barriers — relativization (Baker–Gill–Solovay 1975), natural proofs (Razborov–Rudich 1994), and algebrization (Aaronson–Wigderson 2008) — showing that entire families of known proof techniques cannot, by themselves, resolve the question, which is part of why progress has stalled despite the problem's centrality.
Best known results
- No polynomial-time algorithm is known for any NP-complete problem; the best known algorithms for problems like 3-SAT remain exponential in the worst case.
- Circuit lower bounds have been proved only for restricted models (monotone circuits, bounded-depth circuits), far short of the general circuits needed to separate P from NP.
- Barrier results (relativization, natural proofs, algebrization) show that whole classes of known proof techniques cannot resolve P versus NP on their own.
Tools and where they stop
| Tool | Achieved | Where it stops |
|---|---|---|
| Diagonalization and relativizing arguments | Separates weaker complexity classes (e.g. time hierarchy theorems) | Provably cannot resolve P versus NP itself, since the question does not relativize (Baker–Gill–Solovay 1975) |
| Combinatorial circuit lower bounds | Proves exponential lower bounds for restricted circuit classes such as monotone circuits and AC0 | The natural-proofs barrier (Razborov–Rudich 1994) shows these techniques cannot extend to general circuits, assuming strong pseudorandom generators exist |
Open questions
- Is P = NP, or P ≠ NP?
- If P ≠ NP, are there problems of strictly intermediate complexity between P and NP-complete (Ladner's theorem shows they must exist, but no natural example is known)?
References
- Stephen A. Cook (1971). The complexity of theorem-proving procedures
- Richard M. Karp (1972). Reducibility among combinatorial problems
- Stephen Cook (Clay Mathematics Institute) (2000). P vs NP Problem
- Alexander A. Razborov, Steven Rudich (1997). Natural proofs