P versus NP

10 selected milestones · Source coverage checked 2026-10-10 · Historical annotation and mathematical review remain separate.

1. 1971 publication

   Foundation

   NP-completeness gives a common target

   Cook’s NP-completeness theorem connects SAT to every NP language; Levin’s independent result was published in 1973.

   Scope & review: The reduction framework does not give an efficient SAT algorithm or a lower bound.

   Statements & sources

   • SAT captures P versus NP →

   • Stephen Cook · The P versus NP problem ↗Definition 4, Proposition 1(c) and SAT NP-completeness discussion, pp. 4–5

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

2. 1975 publication

   Foundation

   Conditional existence of intermediate problems

   Ladner shows that, if P ≠ NP, NP contains languages outside both P and the NP-complete class.

   Scope & review: Existence does not settle the premise or classify particular natural candidates.

   Statements & sources

   • If P ≠ NP, intermediate problems exist →

   • Avi Wigderson · Mathematics and Computation ↗Theorem 4.1 [Lad75], §4.2

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

3. Dec 1975 publication

   Proof barrier

   Oracle worlds reveal a proof barrier

   Baker, Gill and Solovay exhibit both equality and inequality with different oracles.

   Scope & review: Methods that relativize cannot decide the ordinary unrelativized question.

   Statements & sources

   • Relativizing techniques cannot settle P versus NP →

   • Baker–Gill–Solovay · Relativizations of the P =? NP question ↗Original paper abstract, SIAM J. Comput. 4(4), 431–442, DOI 10.1137/0204037

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

4. 1994 publication

   Proof barrier

   Natural proofs connect lower bounds to pseudorandomness

   The STOC natural-proofs paper identifies constructivity, largeness and usefulness, with a conditional obstruction for general circuits.

   Scope & review: The strong pseudorandomness premise and exact notion of naturalness remain essential; the journal version appeared in 1997.

   Statements & sources

   • The natural-proofs barrier is conditional →

   • Razborov–Rudich · Natural proofs ↗§2.2 (natural properties), p. 7; hardness definition and Theorem 4.1, p. 15

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

5. 2008 publication

   Proof barrier

   Algebrization identifies another method limitation

   Aaronson and Wigderson define low-degree oracle extensions and show that resolving P versus NP requires techniques outside that framework.

   Scope & review: This is not a ban on algebraic reasoning; the journal version appeared in 2009.

   Statements & sources

   • Algebrizing techniques cannot settle P versus NP →

   • Aaronson–Wigderson · Algebrization ↗§2 definitions; §5 oracle constructions; introduction pp. 3–4

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

6. 2011 publication

   Lower bound

   Algorithms yield ACC circuit lower bounds

   Williams proves NEXP is outside polynomial-size ACC using circuit-analysis algorithms.

   Scope & review: NEXP and ACC restrictions are essential; no NP lower bound for unrestricted circuits follows.

   Statements & sources

   • NEXP has no polynomial-size ACC circuits →

   • Ryan Williams · Non-uniform ACC circuit lower bounds ↗Abstract and main theorem, p. 1

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

7. Mar 15, 2026 preprint

   Lower bound

   A new depth-two threshold lower bound

   Chen, Tal and Wang report n^{2.5−ε} threshold-circuit lower bounds for functions in E^NP.

   Scope & review: For each fixed ε the hard function can differ; E^NP is not NP.

   Statements & sources

   • Depth-two threshold circuits require superquadratic size →

   • Chen–Tal–Wang · Depth-two threshold lower bounds ↗Theorem 1.1, §1.1.1, p. 2

   Historical annotation review: pending. The date refers to the preprint, with the precision supported by the source.

8. Jul 10, 2026 preprint

   Lower bound

   Near-maximum circuit hardness with an oracle and advice

   Ren and Williams obtain Ω(2^n/n) circuit hardness in E^{prMA}/1.

   Scope & review: The promise oracle and one advice bit cannot be dropped from the displayed claim.

   Statements & sources

   • Near-maximum general circuit lower bound in an oracle class →

   • Ren–Williams · Near-maximum circuit lower bounds ↗Theorem 1.1, p. 2

   Historical annotation review: pending. The date refers to the preprint, with the precision supported by the source.

9. Oct 5, 2026 preprint

   Algorithmic advance

   AI-assisted algorithms improve 3SUM and APSP

   Alman and Vassilevska Williams report Claude-discovered algorithms and author-accountable proofs with linked Lean formalizations.

   Scope & review: Fine-grained speedups within polynomial time do not resolve P versus NP.

   Statements & sources

   • A truly subquadratic deterministic 3SUM algorithm →
   • A truly subcubic deterministic APSP algorithm →

   • Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP ↗Theorem 22 using Corollary 26; §1, numeric bounds; Acknowledgments and Methodology
   • Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP ↗Theorem 22; abstract; §1.2; Acknowledgments and Methodology

   Historical annotation review: pending. The date refers to the preprint, with the precision supported by the source.

10. Oct 6, 2026 announcement

    Proposal

    New AI-produced complexity proposals

    OpenAI releases proposed gap reductions, depth-three bounds and algebraic determinantal bounds with scope documents and formal artifacts.

    Scope & review: The proposals have their own assessment; none is a general P versus NP resolution.

    Statements & sources

    • Proposed Unique Games gap reductions →
    • Proposed depth-three bound beyond the square-root exponent →
    • Proposed cubic complex determinantal lower bound →

    • OpenAI · Mathematics release: complexity proposals ↗Family 102; lean/docs/102.md and linked paper/comparator
    • OpenAI · Mathematics release: complexity proposals ↗Family 112; lean/docs/112.md and DepthThree comparator
    • OpenAI · Mathematics release: complexity proposals ↗Family 108; lean/docs/108.md, PermanentCubic comparator; supporting theorem scope excludes ABP consequences

    Historical annotation review: pending. The date refers to the announcement, with the precision supported by the source.