Clay · Millennium Problems ↗
Unsolved · observed Oct 1, 2026 · superseded
Source status date unavailable · observed Oct 1, 2026
The cited source item and version only; this is not an independent OpenMath assessment.
Publication v7
Record details
P versus NP →Coverage & review
Coverage of this curation
Selected P versus NP foundations, conditional implications, circuit lower bounds, proof barriers, related algorithmic advances and recent AI proposals. The timeline is selected, not exhaustive.
Formal proofs: External author/provider formalization links and their stated scope are included. No OpenMath execution, semantic alignment audit or independent reproduction is asserted.
AI-assisted work: Discovery, intermediate theorem contribution and formalization are attributed separately where disclosed. OpenAI proposals and the earlier GPT-4 proof schema do not alter the general status. Not-reported AI involvement does not mean none occurred.
Search scope & review
Clay/Cook; Wigderson’s author text; original relativization, natural-proofs and algebrization papers; Williams; Impagliazzo–Paturi; March and July 2026 primary lower-bound reports; October 2026 algorithm and provider releases; Aletheia and earlier GPT-4 research. Mathematical locators and scope documents were inspected; no novelty or exhaustive-coverage certification is claimed.
Checked Oct 10, 2026 · independent review pending.
- Selected authoritative foundations and recent primary reports; not a complete history or exhaustive literature survey.
- Independent mathematical and logical-relationship review is pending.
- External Lean code is linked as external evidence; OpenMath has not executed or independently reproduced it.
- Restricted-model results and adjacent algorithms are not counted as direct partial resolution; no percentage solved or best-known ranking is inferred.
General status observations
Clay · P versus NP ↗
Unsolved · observed Oct 10, 2026
Source status date unavailable · observed Oct 10, 2026
The canonical classical uniform worst-case decision question P = NP; no supporting theorem decides this status.
Source identities & rights
Clay · Millennium Problems ↗
Clay Mathematics Institute · metadata-link · Not established; links and OpenMath paraphrases only
Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording. Rights / source terms
1 cited entry · exact source identity
- Version
- clay-millennium@observed-2026-10-01
- Revision
- observed-2026-10-01
- Content SHA-256
- No upstream byte snapshot retained; linked metadata only
- Source update
- Unavailable
- Observed
- 2026-10-01
- Check cadence
- 30 days
- https://www.claymath.org/millennium/p-vs-np/ ↗
p-vs-np:entry:0:v1
Clay · P versus NP ↗
Clay Mathematics Institute · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-clay@observed-2026-10-10
- Revision
- observed-2026-10-10
- Content SHA-256
- No upstream byte snapshot retained; linked metadata only
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Page heading: Unsolved; observed 10 October 2026 ↗
pnp-entry-general-status:v1
Stephen Cook · The P versus NP problem ↗
Stephen Cook · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
7 cited entries · exact source identity
- Version
- pnp-cook@official-description-sha256-018f3d473d16
- Revision
- official-description-sha256-018f3d473d16
- Content SHA-256
- 018f3d473d16c35e807e8cdfbd0bed3ccf7a56452e3e10c6b1d84b56eaf2cf59
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Definition 2 and problem statement, pp. 2–3 ↗
pnp-entry-equality:v1 - Problem statement and discussion, pp. 2–3 ↗
pnp-entry-inequality:v1 - Proposition 1(c) and SAT NP-completeness discussion, p. 5 ↗
pnp-entry-sat-in-p:v1 - Definition 4, Proposition 1(c) and SAT NP-completeness discussion, pp. 4–5 ↗
pnp-entry-sat-equivalence:v1 - Proof complexity discussion, pp. 5–6 ↗
pnp-entry-np-conp:v1 - Decision versus search discussion, p. 5 ↗
pnp-entry-np-search:v1 - Definition 4 and Proposition 1(c), pp. 4–5 ↗
pnp-entry-np-complete-hard:v1
Avi Wigderson · Mathematics and Computation ↗
Avi Wigderson · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
9 cited entries · exact source identity
- Version
- pnp-book@author-draft-2019-08-06
- Revision
- author-draft-2019-08-06
- Content SHA-256
- c6b72d0487d31b7d7173266c8d6706649607c6615defb7e2b6c2395782ab1829
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- §5.2.1, Theorem 5.3 and Conjecture 5.4 ↗
pnp-entry-np-circuits:v1 - §5.2.1, Theorem 5.3 ↗
pnp-entry-circuits-imply-separation:v1 - §3.5, NP versus coNP ↗
pnp-entry-conp-implies-separation:v1 - Theorem 5.5 [KL82], §5.2.1 ↗
pnp-entry-karp-lipton:v1 - Theorem 4.1 [Lad75], §4.2 ↗
pnp-entry-ladner:v1 - Definition 4.7 and §4.5 ↗
pnp-entry-one-way:v1 - §4.4–4.5, Definition 4.7 and discussion ↗
pnp-entry-owf-implies-separation:v1 - §12.4, algebraic reductions and completeness ↗
pnp-entry-vp-vnp:v1 - §4.1, polynomial hierarchy; P = NP collapse discussion ↗
pnp-entry-hierarchy-collapse:v1
Baker–Gill–Solovay · Relativizations of the P =? NP question ↗
Theodore Baker; John Gill; Robert Solovay · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-bgs@doi-10.1137/0204037-abstract-observed-2026-10-10
- Revision
- doi-10.1137/0204037-abstract-observed-2026-10-10
- Content SHA-256
- No upstream byte snapshot retained; linked metadata only
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Original paper abstract, SIAM J. Comput. 4(4), 431–442, DOI 10.1137/0204037 ↗
pnp-entry-relativization:v1
Razborov–Rudich · Natural proofs ↗
Alexander Razborov; Steven Rudich · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-rr@STOC-1994-author-paper
- Revision
- STOC-1994-author-paper
- Content SHA-256
- 493cd619b123213f23de32f5075f34d30c563cbd562e025c99b0207568bc1c58
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- §2.2 (natural properties), p. 7; hardness definition and Theorem 4.1, p. 15 ↗
pnp-entry-natural-proofs:v1
Aaronson–Wigderson · Algebrization ↗
Scott Aaronson; Avi Wigderson · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-aw@author-conference-version-observed-2026-10-10
- Revision
- author-conference-version-observed-2026-10-10
- Content SHA-256
- No upstream byte snapshot retained; linked metadata only
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- §2 definitions; §5 oracle constructions; introduction pp. 3–4 ↗
pnp-entry-algebrization:v1
Ryan Williams · Non-uniform ACC circuit lower bounds ↗
Ryan Williams · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-williams@CCC-2011-author-version
- Revision
- CCC-2011-author-version
- Content SHA-256
- 91a09d1ea06fab97e26a791010fd4a902d4be30675998e5bd5e9f8bf68389f80
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Abstract and main theorem, p. 1 ↗
pnp-entry-nexp-acc:v1
Impagliazzo–Paturi · On the complexity of k-SAT ↗
Russell Impagliazzo; Ramamohan Paturi · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
2 cited entries · exact source identity
- Version
- pnp-eth@JCSS-2001
- Revision
- JCSS-2001
- Content SHA-256
- 1b7d20af963735666020e844f8a454fbb64893a5f3b3c488c99d1f4bdae5c11c
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- §1, definition of s_k and the exponential-time hypothesis ↗
pnp-entry-eth:v1 - §1–2, k-SAT exponential complexity and hypothesis ↗
pnp-entry-eth-implies-separation:v1
Chen–Tal–Wang · Depth-two threshold lower bounds ↗
Lijie Chen; Avishay Tal; Yichuan Wang · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-ctw@ECCC-TR26-039-observed-2026-10-10
- Revision
- ECCC-TR26-039-observed-2026-10-10
- Content SHA-256
- b461919916161705a41f43866538d954bd100ca1d4c89451ba734d1caff9987d
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Theorem 1.1, §1.1.1, p. 2 ↗
pnp-entry-threshold-2026:v1
Ren–Williams · Near-maximum circuit lower bounds ↗
Hanlin Ren; Ryan Williams · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-ren@arXiv-2607.09963v1
- Revision
- arXiv-2607.09963v1
- Content SHA-256
- d8f22d2adb4008ac80f0e31c27ffe4025c086e52859978e8e5ce678bc1765b51
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Theorem 1.1, p. 2 ↗
pnp-entry-near-maximum-2026:v1
Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP ↗
Josh Alman; Virginia Vassilevska Williams · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
2 cited entries · exact source identity
- Version
- pnp-claude@arXiv-2610.06783v1
- Revision
- arXiv-2610.06783v1
- Content SHA-256
- d91a79c5dbf1fc662f0c5c1bb2b690ac3d83d9ef5bf872bde4cdaf7cc9e76005
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Theorem 22 using Corollary 26; §1, numeric bounds; Acknowledgments and Methodology ↗
pnp-entry-three-sum-2026:v1 - Theorem 22; abstract; §1.2; Acknowledgments and Methodology ↗
pnp-entry-apsp-2026:v1
OpenAI · Mathematics release: complexity proposals ↗
OpenAI internal model; author attribution per manuscript · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
3 cited entries · exact source identity
- Version
- pnp-openai@fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb
- Revision
- fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb
- Content SHA-256
- No upstream byte snapshot retained; linked metadata only
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Family 102; lean/docs/102.md and linked paper/comparator ↗
pnp-entry-ugc-proposal:v1 - Family 112; lean/docs/112.md and DepthThree comparator ↗
pnp-entry-depth-three-proposal:v1 - Family 108; lean/docs/108.md, PermanentCubic comparator; supporting theorem scope excludes ABP consequences ↗
pnp-entry-permanent-proposal:v1
Robust MDP policy iteration and Aletheia contribution ↗
Ali Asadi; Krishnendu Chatterjee; Ehsan Goharshady; Mehrdad Karrabi; Alipasha Montaseri; Carlo Pagano · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-aletheia@arXiv-2601.23229v2
- Revision
- arXiv-2601.23229v2
- Content SHA-256
- No upstream byte snapshot retained; linked metadata only
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Theorems 20–21, Appendix H; technical contributions §1 ↗
pnp-entry-activity-aletheia:v1
Dong et al. · Large language model for science: P vs NP ↗
Qingxiu Dong; Li Dong; Ke Xu; Guangyan Zhou; Yaru Hao; Zhifang Sui; Furu Wei · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
1 cited entry · exact source identity
- Version
- pnp-gpt4@arXiv-2309.05689v1
- Revision
- arXiv-2309.05689v1
- Content SHA-256
- No upstream byte snapshot retained; linked metadata only
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- Abstract and reported 97-turn dialogue ↗
pnp-entry-activity-gpt4:v1
Cygan et al. · On problems as hard as CNF-SAT ↗
Marek Cygan; Holger Dell; Daniel Lokshtanov; Dániel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh; Magnus Wahlström · metadata-link · Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source. Rights / source terms
2 cited entries · exact source identity
- Version
- pnp-seth@arXiv-1112.2275v3
- Revision
- arXiv-1112.2275v3
- Content SHA-256
- 292ff4c93c0834d4eb560ad0f30b6b703a972901682d5af65b65afcd4c4b0ff1
- Source update
- Unavailable
- Observed
- 2026-10-10
- Check cadence
- 30 days
- §1, Previous Work, p. 1; Theorem 1.1(i) ↗
pnp-entry-seth:v1 - §1 definition; Theorem 1.1(i); immediate consequence using deterministic algorithms as a subclass ↗
pnp-entry-seth-implies-separation:v1
Publication history
- Problem ID
- problem-p-vs-np
- Publication checksum
- 8c8f6e5cdd5d79aff3fe107d7cfdb13bec648cf519b6adea88a7788a3d88c7c6
- Published
- 2026-10-11T03:49:01.379072+00:00
- Publication reason
- Publish checked pilot curation with canonical Claims and scoped progress; preserve exact source revisions, assumptions, coverage limits and historical publications. External artifacts and OpenMath execution remain distinct.
- Version 1 · Sep 30, 2026
Initial checked pilot publication; source attribution, rights, wording and coverage reviewed by OpenMath staff.
- Version 2 · Oct 10, 2026
Add cited resolution scope and consolidate equivalent prime formulations and supporting Claims; mathematical evidence and execution review remain distinct.
- Version 3 · Oct 10, 2026
Publish checked pilot curation with canonical Claims and scoped progress; preserve exact source revisions, assumptions, coverage limits and historical publications. External artifacts and OpenMath execution remain distinct.
- Version 4 · Oct 10, 2026
Publish checked pilot curation with canonical Claims and scoped progress; preserve exact source revisions, assumptions, coverage limits and historical publications. External artifacts and OpenMath execution remain distinct.
- Version 5 · Oct 10, 2026
Expose exact scoped quantitative bounds in concise progress summaries; preserve mathematical Claims and earlier source versions.
- Version 6 · Oct 11, 2026
Publish checked pilot curation with canonical Claims and scoped progress; preserve exact source revisions, assumptions, coverage limits and historical publications. External artifacts and OpenMath execution remain distinct.
- Version 7 · Oct 11, 2026
Publish checked pilot curation with canonical Claims and scoped progress; preserve exact source revisions, assumptions, coverage limits and historical publications. External artifacts and OpenMath execution remain distinct.
- Version 8 · Oct 11, 2026
Publish checked pilot curation with canonical Claims and scoped progress; preserve exact source revisions, assumptions, coverage limits and historical publications. External artifacts and OpenMath execution remain distinct.
- Version 9 · Oct 12, 2026
Reviewed reader correction: preserve assertion history, exact citations and scoped assessments; task evidence names its exact Claim target.
- Version 10 · Oct 13, 2026
Reviewed reader correction: preserve assertion history, exact citations and scoped assessments; task evidence names its exact Claim target.
- Version 11 · Oct 13, 2026
Reviewed reader correction: preserve assertion history, exact citations and scoped assessments; task evidence names its exact Claim target.
- Version 12 · Oct 15, 2026
Reviewed reader correction: preserve assertion history, exact citations and scoped assessments; task evidence names its exact Claim target.
- Version 13 · Oct 20, 2026
Reviewed reader correction: preserve assertion history, exact citations and scoped assessments; task evidence names its exact Claim target.
- Version 14 · Oct 20, 2026
Reviewed reader correction: preserve assertion history, exact citations and scoped assessments; task evidence names its exact Claim target.