openmath.dev
Esc

Loading…

↑ ↓ to move↵ to open

Appearance
Appearance
← Problems

Theoretical computer science · Question

P versus NP

Can every decision problem with polynomially bounded, polynomial-time-checkable certificates also be decided in deterministic polynomial time?

Openper Clay · P versus NP · checked Oct 10, 2026
Cite & export
Open this versionExport record · JSONRecord detailsReport a correction
Use with an agent

Overview

Known

The general question remains open. Known restricted-model lower bounds, proof barriers and conditional implications explain the frontier; related faster algorithms do not settle P versus NP.

Open questions

No general deterministic polynomial-time algorithm for SAT, and no proof that an NP language requires superpolynomial deterministic time, is established by this selected curation.

Latest

Precise statement

Uniform classical deterministic computation on finite binary inputs, with worst-case polynomial time in input bit length. NP certificates have polynomial length. Randomized, quantum, nonuniform, average-case and restricted-circuit questions have their own scopes.

Definitions

Decision problem and certificate
A decision problem has a yes-or-no answer. NP permits a polynomially bounded certificate for a yes answer that can be checked in polynomial time.

How to read this question

What would settle this question?

A deterministic polynomial-time algorithm for SAT establishes equality. Proving any language in NP is outside P establishes inequality. These are two possible answers to the same question.

Limit A restricted circuit lower bound, successful finite experiment or new hardness reduction does not meet either criterion.

Sources & review

Supporting statements

Source-grounded explanation · independent explanation review: pending.

Checking, finding and practical efficiency

NP means nondeterministic polynomial time, not “non-polynomial.” Certificates have polynomial length. The question concerns all input lengths and worst-case guarantees; fixed-size puzzles and benchmark performance have narrower scopes.

Limit Even polynomial time may have impractical exponents or constants. Quantum, average-case and nonuniform models are different questions.

Sources & review

Supporting statements

Source-grounded explanation · independent explanation review: pending.

Question paraphrased by OpenMath. Original wording is available in the sources.

Landscape

Figures and explorable examples. Selecting a statement opens its exact wording.

Visual setup

The two possible worlds

Exactly one of these pictures is true, and the question is which. Each region and consequence is a proved conditional statement; select one to read it exactly.

Reading boundary. The pictures are schematic: region sizes mean nothing, and neither world is asserted. The conditional statements are proved; which premise holds is the open problem.

If P ≠ NP

If P ≠ NP○ Open

NP

NP-complete: outside P● Proved under stated assumptions
NP-intermediate (Ladner)● Proved under stated assumptions

P

If P = NP

If P = NP○ Open

P = NP

Consequences

Witnesses can be found efficiently● Proved under stated assumptionsThe polynomial hierarchy collapses to P● Proved under stated assumptions
In either world: P = NP exactly when SAT is in P● Proved under stated assumptions
Text version

If P ≠ NP, the class P sits strictly inside NP: NP-complete problems lie outside P, and some problems in NP are neither in P nor NP-complete (Ladner). If P = NP, the three coincide: witnesses can be found efficiently and the polynomial hierarchy collapses to P. In either world, P = NP holds exactly when SAT is in P.

Deterministic polynomial time; NP-completeness under polynomial-time many-one reductions. Each region states a proved implication from its world's premise; the premises themselves are open.

  1. If P ≠ NP

    Open

    P ≠ NP

    The conjectural negative answer to the same canonical question.

    P ≠ NP →

  2. NP-complete: outside P

    Proved

    If P ≠ NP, NP-complete problems have no polynomial algorithm

    Rules out uniform polynomial-time algorithms, not efficient restricted-instance methods or heuristics.

    If P ≠ NP, NP-complete problems have no polynomial algorithm →

  3. NP-intermediate (Ladner)

    Proved

    If P ≠ NP, intermediate problems exist

    Existence of NP-intermediate languages; not a classification of specific natural candidates.

    If P ≠ NP, intermediate problems exist →

  4. If P = NP

    Open

    P = NP

    The affirmative answer to the canonical question.

    P = NP →

  5. Witnesses can be found efficiently

    Proved

    If P = NP, NP witnesses can be found efficiently

    An asymptotic search consequence for these relations; output length and encoding restrictions matter.

    If P = NP, NP witnesses can be found efficiently →

  6. The polynomial hierarchy collapses to P

    Proved

    If P = NP, the polynomial hierarchy collapses to P

    An asymptotic complexity-class consequence, not a practical algorithm implementation.

    If P = NP, the polynomial hierarchy collapses to P →

  7. In either world: P = NP exactly when SAT is in P

    Proved

    SAT captures P versus NP

    An established equivalence between two unresolved assertions.

    SAT captures P versus NP →

Sources & review

Authored by OpenMath curation on 2026-10-21 (AI-assisted curation). Independent review of this visual explanation is pending; linked assertions and relationships have their own assessments.

Visual setup

How far circuit lower bounds reach

Proved lower bounds sit in restricted circuit models or for functions in classes much larger than NP. The target, superpolynomial general circuits for NP, is behind three proved barriers.

Reading boundary. The horizontal order is by circuit model only. A mark further right is not a step towards NP: the hard functions belong to larger or oracle classes, and none of the marks transfers to NP. Barriers rule out techniques, not the statement.

Proved

NEXP: no polynomial-size ACC⁰ circuits● Proved under stated assumptions
ENP: size n(2.5−ε) needed● Proved under stated assumptions
EprMA/1: size Ω(2ⁿ/n) needed● Proved under stated assumptions

Barriers: techniques proved unable to reach the target

Relativization● Proved under stated assumptionsNatural proofs● Proved under stated assumptionsAlgebrization● Proved under stated assumptions

Open target

NP: superpolynomial size needed (open)○ Open

ACC⁰ · constant depth

Depth-two threshold

General circuits

Circuit model, weaker to stronger

Text version

Circuit models run from constant depth with counting gates (ACC⁰), through depth-two threshold circuits, to unrestricted Boolean circuits. Marks are proved lower bounds, each labelled with the class containing the hard function: NEXP against ACC⁰, E^NP against depth-two threshold circuits of size n^(2.5−ε), and an oracle class E^{prMA}/1 against general circuits of size Ω(2ⁿ/n). The open target is NP against general circuits of polynomial size, which would imply P ≠ NP. Relativizing, natural and algebrizing techniques provably cannot reach it.

Nonuniform Boolean circuit families; sizes as in each cited theorem. A mark names the hard function's class; marks for different classes are not ordered against each other.

  1. NEXP: no polynomial-size ACC⁰ circuits

    Proved

    NEXP has no polynomial-size ACC circuits

    NEXP is outside nonuniform polynomial-size ACC: constant-depth circuits with fixed-modulus counting gates.

    Limit. Nondeterministic exponential time versus restricted nonuniform circuits; not an NP lower bound against unrestricted circuits.

    NEXP has no polynomial-size ACC circuits →

  2. ENP: size n(2.5−ε) needed

    Proved

    Depth-two threshold circuits require superquadratic size

    For each fixed ε > 0, an E^NP function needs depth-two threshold size n^{2.5−ε}; the function may depend on ε.

    Limit. The hard function may depend on ε; its class is E^NP, not NP.

    Depth-two threshold circuits require superquadratic size →

  3. EprMA/1: size Ω(2ⁿ/n) needed

    Proved

    Near-maximum general circuit lower bound in an oracle class

    An E^{prMA}/1 function needs Ω(2^n/n) general Boolean circuit size, retaining its promise oracle and one advice bit.

    Limit. An oracle/advice class above the target NP; no general NP separation follows.

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

  4. Relativization

    Proved

    Relativizing techniques cannot settle P versus NP

    Relativizing techniques cannot settle P versus NP.

    Limit. A limitation of relativizing proofs for the unrelativized question.

    Relativizing techniques cannot settle P versus NP →

  5. Natural proofs

    Proved

    The natural-proofs barrier is conditional

    The natural-proofs barrier is conditional.

    Limit. A conditional barrier for this precise kind of circuit-lower-bound method; not for all mathematical proofs.

    The natural-proofs barrier is conditional →

  6. Algebrization

    Proved

    Algebrizing techniques cannot settle P versus NP

    Algebrizing techniques cannot settle P versus NP.

    Limit. A proved limitation of a specified framework, not every algebraic method.

    Algebrizing techniques cannot settle P versus NP →

  7. NP: superpolynomial size needed (open)

    Open

    NP lacks polynomial-size general circuits

    A stronger circuit-complexity target than P ≠ NP.

    NP lacks polynomial-size general circuits →

Sources & review

Authored by OpenMath curation on 2026-10-21 (AI-assisted curation). Independent review of this visual explanation is pending; linked assertions and relationships have their own assessments.

Results

The question 2

  • Open
    P = NP

    The affirmative answer to the canonical question.

  • Open
    P ≠ NP

    The conjectural negative answer to the same canonical question.

Equivalent formulations 2

  • Open
    SAT in polynomial time

    The SAT decision target; presently unresolved.

  • Proved
    SAT captures P versus NP

    An established equivalence between two unresolved assertions.

    Cook

Proposed 3

  • Proposed
    Proposed Unique Games gap reductions

    Provider proposal for Unique Games hardness; a hardness reduction does not prove P ≠ NP.

    OpenAI internal model 2026
  • Proposed
    Proposed depth-three bound beyond the square-root exponent

    Restricted depth only; not a fixed n1/2+ε exponent and not unrestricted circuits.

    OpenAI internal model 2026
  • Proposed
    Proposed cubic complex determinantal lower bound

    A proposed bound in an algebraic model; does not separate VP from VNP or Boolean P from NP.

    OpenAI internal model 2026

Conditional implications 10

  • Proved
    General NP circuit lower bounds would separate P and NP

    If NP is not contained in P/poly, then P ≠ NP.

    Wigderson 2019
  • Proved
    NP versus coNP would separate P and NP

    If NP ≠ coNP, then P ≠ NP.

    Wigderson 2019
  • Proved
    Polynomial NP circuits would collapse the hierarchy

    If NP is contained in P/poly, then PH = Σ₂P.

    Wigderson 2019
  • Proved
    If P ≠ NP, intermediate problems exist

    If P ≠ NP, then some languages in NP are neither in P nor NP-complete under polynomial-time many-one reductions.

    Wigderson 2019
  • Proved
    One-way functions would separate P and NP

    If standard one-way functions exist, then P ≠ NP.

    Wigderson 2019
  • Proved
    ETH would separate P and NP

    If ETH holds, then P ≠ NP.

    Impagliazzo & Paturi 2001
  • Proved
    Randomized SETH would separate P and NP

    If the stated bounded-error randomized SETH holds, then P ≠ NP.

    Cygan et al. 2014
  • Proved
    If P = NP, NP witnesses can be found efficiently

    If P = NP, then every polynomially balanced, polynomial-time-decidable witness relation admits polynomial-time witness search or correct reporting that no witness exists.

    Cook
  • Proved
    If P = NP, the polynomial hierarchy collapses to P

    If P = NP, then PH = P.

    Wigderson 2019
  • Proved
    If P ≠ NP, NP-complete problems have no polynomial algorithm

    If P ≠ NP, every NP-complete decision language is outside P.

    Cook

Proof barriers 3

  • Proved
    Relativizing techniques cannot settle P versus NP

    Relativizing techniques cannot settle P versus NP.

    Baker et al. 1975
  • Proved
    The natural-proofs barrier is conditional

    The natural-proofs barrier is conditional.

    Razborov & Rudich 1994
  • Proved
    Algebrizing techniques cannot settle P versus NP

    Algebrizing techniques cannot settle P versus NP.

    Aaronson & Wigderson 2008

Restricted-model lower bounds 3

  • Proved
    NEXP has no polynomial-size ACC circuits

    NEXP is outside nonuniform polynomial-size ACC: constant-depth circuits with fixed-modulus counting gates.

    Williams 2011
  • Proved
    Depth-two threshold circuits require superquadratic size

    For each fixed ε > 0, an ENP function needs depth-two threshold size n2.5−ε; the function may depend on ε.

    Chen et al. 2026
  • Proved
    Near-maximum general circuit lower bound in an oracle class

    An EprMA/1 function needs Ω(2n/n) general Boolean circuit size, retaining its promise oracle and one advice bit.

    Ren & Williams 2026

Related advances 2

  • Proved
    A truly subquadratic deterministic 3SUM algorithm

    Deterministic 3SUM in O(n1.9992) for polynomially bounded integers, in the cited integer-operation model.

    Alman & Williams 2026
  • Proved
    A truly subcubic deterministic APSP algorithm

    Deterministic APSP in O(n2.9995) for fixed polynomial integer-weight bounds and no negative cycles.

    Alman & Williams 2026

Variants and analogues 6

  • Open
    NP lacks polynomial-size general circuits

    A stronger circuit-complexity target than P ≠ NP.

  • Open
    NP ≠ coNP

    A stronger related separation; not equivalent to P ≠ NP.

  • Open
    Standard one-way functions exist

    Average-case cryptographic hardness; stronger than merely worst-case NP hardness.

  • Open
    Exponential Time Hypothesis

    A stronger quantitative hypothesis than P ≠ NP.

  • Open
    VP versus VNP

    An algebraic analogue; no equivalence to Boolean P versus NP is asserted.

  • Open
    Strong Exponential Time Hypothesis — randomized version

    A fine-grained hardness premise stronger than the deterministic version; neither version follows from P ≠ NP.

Connections

How the recorded statements connect
⇔impliesimpliesimpliesimpliesimpliesanalogueGeneral NP circuit lower bounds · OpenGeneral NP circuit lowerbounds○ OpenNP ≠ coNP · OpenNP ≠ coNP○ OpenOne-way functions exist · OpenOne-way functions exist○ OpenExponential Time Hypothesis · OpenExponential Time Hypothesis○ OpenRandomized Strong Exponential Time Hypothesis · OpenRandomized Strong ExponentialTime Hypothesis○ OpenVP versus VNP · OpenVP versus VNP○ OpenP ≠ NP · OpenP ≠ NP○ OpenP = NP · OpenP = NP○ OpenSAT in polynomial time · OpenSAT in polynomial time○ Open
  • ━ ⇔ equivalent
  • → implies
  • ┅ analogue or related (no logical link)
  • Border colour = status
Curated map with reading notes

Selected connections

How the complexity questions connect

A selected map of equivalence, one-way implications and a different-model analogue. Open premises remain open.

Reading boundary. This is a selected relations map, not the full landscape of complexity classes. An established implication does not prove its open statements. P ≠ NP alone does not imply one-way functions, ETH or the displayed stronger lower bounds. Barriers and restricted-model progress remain in their existing sections.

Equivalent formulations with target SAT in polynomial time. Equivalence does not prove either statement.

P = NPStatement: Open

The equivalence relates the answers; it does not prove either statement. Inspect their separate assessments.

One-way implications with target P ≠ NP. Each premise separately implies the target; no reverse implication is asserted.

NP ⊄ P/polyPremise: OpenNP ≠ coNPPremise: Open

Each source implies the target under its stated assumptions. The map asserts no reverse implication.

More connections · 4

One-way implications with target P ≠ NP. Each premise separately implies the target; no reverse implication is asserted.

One-way functions existPremise: OpenETHPremise: OpenRandomized SETHPremise: Open

Each source implies the target under its stated assumptions. The map asserts no reverse implication.

Different-model analogue with target P ≠ NP. No implication is asserted.

VP versus VNPStatement: Open

Different mathematical model. This connection asserts no implication in either direction.

Text version

P = NP is equivalent to SAT having a polynomial-time algorithm. The selected circuit lower-bound, NP versus coNP, one-way-function, ETH and randomized-SETH assertions each imply P ≠ NP under their exact formulations. VP versus VNP is a different-model analogue, not an implication. Supporting implication theorems do not establish their premises or either answer to P versus NP.

Classical uniform deterministic worst-case polynomial time for the canonical question. Each stronger premise retains its own nonuniform, randomized or average-case assumptions on its Claim page.

  1. P = NP — SAT in polynomial time

    Equivalent formulations · independent relationship review pending

    P = NP ⇔ SAT in polynomial time

    SAT is an equivalent decision target: a deterministic polynomial-time SAT algorithm establishes P = NP.

    Limit. The equivalence is established; both target assertions remain unresolved.

    Supporting relationship theorem SAT captures P versus NP → Proved
  2. NP lacks polynomial-size general circuits — P ≠ NP

    One-way implications · independent relationship review pending

    NP lacks polynomial-size general circuits ⇒ P ≠ NP

    Nonuniform general NP circuit lower bounds would suffice for P ≠ NP.

    Limit. The reverse implication is not established; restricted gates or larger target classes do not satisfy this premise.

    Supporting relationship theorem General NP circuit lower bounds would separate P and NP → Proved
  3. NP ≠ coNP — P ≠ NP

    One-way implications · independent relationship review pending

    NP ≠ coNP ⇒ P ≠ NP

    Separating NP from coNP would also separate P from NP.

    Limit. The converse is not established; short proofs in one particular proof system are a narrower question.

    • NP ≠ coNP →Open

      A stronger related separation; not equivalent to P ≠ NP.

    • P ≠ NP →Open

      The conjectural negative answer to the same canonical question.

    Supporting relationship theorem NP versus coNP would separate P and NP → Proved
  4. Standard one-way functions exist — P ≠ NP

    One-way implications · independent relationship review pending

    Standard one-way functions exist ⇒ P ≠ NP

    Average-case one-wayness is a stronger sufficient hardness premise.

    Limit. P ≠ NP alone does not establish one-way functions or the security of a particular cryptosystem.

    Supporting relationship theorem One-way functions would separate P and NP → Proved
  5. Exponential Time Hypothesis — P ≠ NP

    One-way implications · independent relationship review pending

    Exponential Time Hypothesis ⇒ P ≠ NP

    ETH rules out even subexponential 3SAT algorithms in the stated model.

    Limit. P ≠ NP does not by itself establish exponential runtime lower bounds.

    Supporting relationship theorem ETH would separate P and NP → Proved
  6. Strong Exponential Time Hypothesis — randomized version — P ≠ NP

    One-way implications · independent relationship review pending

    Strong Exponential Time Hypothesis — randomized version ⇒ P ≠ NP

    The cited randomized SETH excludes even fixed-base exponential improvements for some clause width, and therefore excludes polynomial deterministic algorithms.

    Limit. This version is stronger than deterministic SETH; neither is implied by P ≠ NP.

    Supporting relationship theorem Randomized SETH would separate P and NP → Proved
  7. VP versus VNP — P ≠ NP

    Different-model analogue · independent relationship review pending

    VP versus VNP · P ≠ NP

    VP versus VNP is an algebraic complexity analogue, with field operations and polynomial families.

    Limit. No equivalence or implication to the classical Boolean question is asserted.

    • VP versus VNP →Open

      An algebraic analogue; no equivalence to Boolean P versus NP is asserted.

    • P ≠ NP →Open

      The conjectural negative answer to the same canonical question.

  8. P = NP

    Open

    P = NP

    The affirmative answer to the canonical question.

    P = NP →

  9. SAT in polynomial time

    Open

    SAT in polynomial time

    The SAT decision target; presently unresolved.

    SAT in polynomial time →

  10. P ≠ NP

    Open

    P ≠ NP

    The conjectural negative answer to the same canonical question.

    P ≠ NP →

  11. NP ⊄ P/poly

    Open

    NP lacks polynomial-size general circuits

    A stronger circuit-complexity target than P ≠ NP.

    NP lacks polynomial-size general circuits →

  12. NP ≠ coNP

    Open

    NP ≠ coNP

    A stronger related separation; not equivalent to P ≠ NP.

    NP ≠ coNP →

  13. One-way functions exist

    Open

    Standard one-way functions exist

    Average-case cryptographic hardness; stronger than merely worst-case NP hardness.

    Standard one-way functions exist →

  14. ETH

    Open

    Exponential Time Hypothesis

    A stronger quantitative hypothesis than P ≠ NP.

    Exponential Time Hypothesis →

  15. Randomized SETH

    Open

    Strong Exponential Time Hypothesis — randomized version

    A fine-grained hardness premise stronger than the deterministic version; neither version follows from P ≠ NP.

    Strong Exponential Time Hypothesis — randomized version →

  16. VP versus VNP

    Open

    VP versus VNP

    An algebraic analogue; no equivalence to Boolean P versus NP is asserted.

    VP versus VNP →

Sources & review

Authored by OpenMath curation on 2026-10-11 (AI-assisted curation). Independent review of this visual explanation is pending; linked assertions and relationships have their own assessments.

7 connections · 4 consequences. Select a statement in the graph to show only its entries.

Equivalent formulations 1

Implications 5

Analogues and related questions 1

Consequences 4

Assuming P = NPOpen

Assuming P ≠ NPOpen

  • Worst-case limits guide algorithm design

    Conditional

    If P ≠ NP, NP-complete decision problems admit no uniform deterministic polynomial-time algorithms. Restricted instances, approximation, parameterization and heuristics still have meaningful roles.

    Limit This is a worst-case asymptotic statement; it does not say every instance is hard or that a particular deployed cryptosystem is secure.

    Sources & review

    If P ≠ NP, every NP-complete decision language is outside P.

    This follows from the definition of NP-completeness under the separation premise.

    Assumptions & sources

    Source-grounded explanation · independent explanation review: pending.

Approaches

How the problem is attacked, and what each line of attack cannot yet reach.

Circuit lower bounds and algorithmic methods

A polynomial-time algorithm has polynomial-size circuits. General NP circuit lower bounds would suffice, while Williams’ algorithmic method has delivered lower bounds in restricted circuits for larger classes.

Cannot yet reach Moving to unrestricted circuits and a target in NP is a substantive missing step.

Sources & review

Supporting statements

Source-grounded explanation · independent explanation review: pending.

Understand which proof properties encounter barriers

Relativization, natural proofs and algebrization identify precise limitations. They help diagnose a proposed method, with the natural-proofs obstruction additionally depending on strong pseudorandomness.

Cannot yet reach These are not universal impossibility results for all proof methods; avoiding a barrier does not itself prove a separation.

Sources & review

Supporting statements

Source-grounded explanation · independent explanation review: pending.

Algebraic and proof-complexity routes

VP versus VNP studies polynomial families under arithmetic computation. NP versus coNP motivates proof-complexity routes. Both connect to the Boolean question through specific scopes rather than shared names.

Cannot yet reach A result for one arithmetic representation or one propositional proof system does not automatically settle either general separation.

Sources & review

Supporting statements

Source-grounded explanation · independent explanation review: pending.

Timeline

  1. New AI-produced complexity proposalsProposal

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

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

  2. AI-assisted algorithms improve 3SUM and APSPAlgorithmic advance

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

    Fine-grained speedups within polynomial time do not resolve P versus NP.

  3. Near-maximum circuit hardness with an oracle and adviceLower bound

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

    The promise oracle and one advice bit cannot be dropped from the displayed claim.

  4. A new depth-two threshold lower boundLower bound

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

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

  5. Algorithms yield ACC circuit lower boundsLower bound

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

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

  6. Algebrization identifies another method limitationProof barrier

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

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

  7. Natural proofs connect lower bounds to pseudorandomnessProof barrier

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

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

  8. Oracle worlds reveal a proof barrierProof barrier

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

    Methods that relativize cannot decide the ordinary unrelativized question.

  9. Conditional existence of intermediate problemsFoundation

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

    Existence does not settle the premise or classify particular natural candidates.

  10. NP-completeness gives a common targetFoundation

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

    The reduction framework does not give an efficient SAT algorithm or a lower bound.

Full history with sources →

Evidence

Literature

8 published papers · 5 preprints · 2 projects

Status per Clay · P versus NP · checked Oct 10, 2026.

  • Open: Clay · P versus NP · Unsolved ↗ · source date not recorded · checked Oct 10, 2026The canonical classical uniform worst-case decision question P = NP; no supporting theorem decides this status.
Formal

None linked

Reported in sources: External author/provider formalization links and their stated scope are included. No OpenMath execution, semantic alignment audit or independent reproduction is asserted.

Computation

None recorded

Review

Not yet reviewed

Collection last checked Oct 10, 2026.

Sources

Choose a starting point below. Each result links to its exact statement, cited passages and checks.

Start here

Bibliography 16

Research activity · 2 entries

Research direction

Robust MDP policy iteration and Aletheia contribution

Aletheia supplies an effective strengthening of a combinatorial bound used in robust-MDP context; the authors’ preceding theorem already suffices.

The algorithmic scope fixes L∞ uncertainty and a constant discount factor; the AI contribution is an intermediate theorem, not P versus NP.

Robust MDP policy iteration and Aletheia contribution · sources & artifacts →

Selected literature; source observations and coverage limits are retained in the publication details.

Contributors

Classical barriers are credited to Baker–Gill–Solovay, Razborov–Rudich and Aaronson–Wigderson. Williams and later author teams provide the scoped advances. Disclosed AI contributions are attributed separately by source.

Authors & roles

Clay · P versus NP →

Clay Mathematics Institute

AI involvement is not reported by this cited source; this is not a claim of its absence.

OpenAI · Mathematics release: complexity proposals →

OpenAI internal model; author attribution per manuscript

OpenAI reports internal-model production and accompanying formalizations at mixed stages of assessment. These Claims remain proposed in this curation; external formal evidence does not become an OpenMath check.

Robust MDP policy iteration and Aletheia contribution →

Ali Asadi · Krishnendu Chatterjee · Ehsan Goharshady · Mehrdad Karrabi · Alipasha Montaseri · Carlo Pagano

The source credits Aletheia/Gemini Deep Think with an effective strengthening, Theorem 21, of an intermediate combinatorial result; the authors’ Theorem 20 already suffices for their complexity analysis.

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

The authors report a GPT-4 dialogue producing a proposed P ≠ NP proof schema. A dialogue and self-evaluation are not an accepted proof or independent verification.

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

AI involvement is not reported by this cited source; this is not a claim of its absence.

These are source credits; they do not imply OpenMath accounts, endorsements or independent mathematical review.

Record details
Record version
14
Classification
MSC2020 68Q15
Prerequisite level
undergraduate
Source observations & version history →