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

Literature: 8 published papers · 5 preprints · 2 projects
Formal: None linked
Computation: None recorded
Review: Not yet reviewed

Use with an agent

Earlier version 9 of this page. View current →

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

New AI-produced complexity proposalsOct 6, 2026Proposed
AI-assisted algorithms improve 3SUM and APSPOct 5, 2026

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.

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.

SAT captures P versus NP (Proved)
P ≠ NP (Open)

Sources & review

Supporting statements

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

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.

P = NP (Open)
If P = NP, NP witnesses can be found efficiently (Proved)

Sources & review

Supporting statements

Stephen Cook · The P versus NP problem ↗Definition 2 and problem statement, pp. 2–3
Stephen Cook · The P versus NP problem ↗Decision versus search discussion, p. 5

Source-grounded explanation · independent explanation review: pending.

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

Results

The question 2

Equivalent formulations 2

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
Theorem · Different statement · related variant
ProposedOpenAI internal model 2026
Proposed Unique Games gap reductions
For every fixed ε, δ in (0,1/2), there is a deterministic polynomial-time reduction from binary 3SAT to unique games over a fixed alphabet, with completeness at least 1−ε and soundness at most δ.
Assumptions
- Alphabet depends on ε and δ; translation constraints in the provider’s formalization scope.
In this problem
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Provider proposal for Unique Games hardness; a hardness reduction does not prove P ≠ NP.
Sources
- OpenAI · Mathematics release: complexity proposals →
Open statement page →
Proposed
Proposed depth-three bound beyond the square-root exponent
Restricted depth only; not a fixed n^1/2+ε exponent and not unrestricted circuits.
OpenAI internal model 2026
Bound · Restricted-model result
ProposedOpenAI internal model 2026
Proposed depth-three bound beyond the square-root exponent
A fixed language in P requires more than 2^{A√n} depth-three OR–AND–OR gates for every fixed A > 0, at every sufficiently large input length.
Assumptions
- Unbounded finite fan-in and sharing; free input negations and constants; total gate count; exact computation.
In this problem
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Restricted depth only; not a fixed n^{1/2+ε} exponent and not unrestricted circuits.
Sources
- OpenAI · Mathematics release: complexity proposals →
Open statement page →
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
Bound · Different statement · related variant
ProposedOpenAI internal model 2026
Proposed cubic complex determinantal lower bound
For m ≥ 1408, every affine-linear determinant representation, including coefficientwise limits, of the complex m×m permanent has size at least m^3/(5529600e).
Assumptions
- Complex numbers; exact and border affine-linear determinantal representations.
In this problem
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
A proposed bound in an algebraic model; does not separate VP from VNP or Boolean P from NP.
Sources
- OpenAI · Mathematics release: complexity proposals →
Open statement page →

Conditional implications 10

Proof barriers 3

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
Theorem · Restricted-model result
ProvedWilliams 2011
NEXP has no polynomial-size ACC circuits
NEXP is not contained in nonuniform polynomial-size ACC.
Assumptions
- Constant circuit depth; unbounded fan-in AND, OR, NOT and MOD_m gates for a fixed integer m > 1.
In this problem
NEXP is outside nonuniform polynomial-size ACC: constant-depth circuits with fixed-modulus counting gates.
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Nondeterministic exponential time versus restricted nonuniform circuits; not an NP lower bound against unrestricted circuits.
Sources
- Ryan Williams · Non-uniform ACC circuit lower bounds →
Open statement page →
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 ε.
Chen et al. 2026
Theorem · Restricted-model result
ProvedChen et al. 2026
Depth-two threshold circuits require superquadratic size
For every fixed ε in (0,1), there exists a function f in E^NP not computable by depth-two THR∘THR circuits of size n^{2.5−ε}; the same holds for SYM∘THR.
Assumptions
- ε is fixed; circuit size counts gates under the paper’s convention; arbitrary linear threshold gates.
In this problem
For each fixed ε > 0, an E^NP function needs depth-two threshold size n^{2.5−ε}; the function may depend on ε.
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
The hard function may depend on ε; its class is E^NP, not NP.
Sources
- Chen–Tal–Wang · Depth-two threshold lower bounds →
Open statement page →
Proved
Near-maximum general circuit lower bound in an oracle class
An E^prMA/1 function needs Ω(2ⁿ/n) general Boolean circuit size, retaining its promise oracle and one advice bit.
Ren & Williams 2026
Theorem · Restricted-model result
ProvedRen & Williams 2026
Near-maximum general circuit lower bound in an oracle class
There exists a function in E^{prMA}/1 requiring Boolean circuits of size Ω(2^n/n).
Assumptions
- Deterministic exponential time with a promise-MA oracle; one bit of advice; the algorithm queries promised instances on the correct advice bit.
In this problem
An E^{prMA}/1 function needs Ω(2^n/n) general Boolean circuit size, retaining its promise oracle and one advice bit.
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
An oracle/advice class above the target NP; no general NP separation follows.
Sources
- Ren–Williams · Near-maximum circuit lower bounds →
Open statement page →

Related advances 2

Proved
A truly subquadratic deterministic 3SUM algorithm
Deterministic 3SUM in O(n^1.9992) for polynomially bounded integers, in the cited integer-operation model.
Alman & Williams 2026
Theorem · Related result
ProvedAlman & Williams 2026
A truly subquadratic deterministic 3SUM algorithm
For every fixed ν, 3SUM on n integers with absolute value at most n^ν has a deterministic O(n^{1.9992})-time algorithm in the paper’s integer-operation model.
Assumptions
- Polynomially bounded integers; fixed ν; the algorithm and model of Theorem 22 and Corollary 26.
In this problem
Deterministic 3SUM in O(n^{1.9992}) for polynomially bounded integers, in the cited integer-operation model.
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
A fine-grained improvement for a problem already solvable in polynomial time; no SAT speedup or P versus NP resolution is claimed.
Sources
- Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP →
Open statement page →
Proved
A truly subcubic deterministic APSP algorithm
Deterministic APSP in O(n^2.9995) for fixed polynomial integer-weight bounds and no negative cycles.
Alman & Williams 2026
Theorem · Related result
ProvedAlman & Williams 2026
A truly subcubic deterministic APSP algorithm
For every fixed ν, all-pairs shortest paths on directed n-vertex graphs with integer edge weights of absolute value at most n^ν and no negative cycles can be computed deterministically in O(n^{2.9995}) time.
Assumptions
- Fixed polynomial weight bound; directed graphs with no negative cycles; the integer-operation model of Theorem 22.
In this problem
Deterministic APSP in O(n^{2.9995}) for fixed polynomial integer-weight bounds and no negative cycles.
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
A fine-grained algorithmic improvement within polynomial time; real-weight and randomized variants have separate guarantees.
Sources
- Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP →
Open statement page →

Variants and analogues 6

Connections

How the recorded statements connect

━ ⇔ 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

SAT in polynomial time○ 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: Open NP ≠ coNPPremise: Open

P ≠ NP○ 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: Open ETHPremise: Open Randomized SETHPremise: Open

P ≠ NP○ 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

P ≠ NP○ 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.

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.
- P = NP →Open
  The affirmative answer to the canonical question.
- SAT in polynomial time →Open
  The SAT decision target; presently unresolved.
Supporting relationship theorem SAT captures P versus NP → Proved
- Stephen Cook · The P versus NP problemDefinition 4, Proposition 1(c) and SAT NP-completeness discussion, pp. 4–5PublishedOriginal passage ↗
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.
- NP lacks polynomial-size general circuits →Open
  A stronger circuit-complexity target than P ≠ NP.
- P ≠ NP →Open
  The conjectural negative answer to the same canonical question.
Supporting relationship theorem General NP circuit lower bounds would separate P and NP → Proved
- Avi Wigderson · Mathematics and Computation§5.2.1, Theorem 5.3PublishedOriginal passage ↗
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
- Avi Wigderson · Mathematics and Computation§3.5, NP versus coNPPublishedOriginal passage ↗
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.
- Standard one-way functions exist →Open
  Average-case cryptographic hardness; stronger than merely worst-case NP hardness.
- P ≠ NP →Open
  The conjectural negative answer to the same canonical question.
Supporting relationship theorem One-way functions would separate P and NP → Proved
- Avi Wigderson · Mathematics and Computation§4.4–4.5, Definition 4.7 and discussionPublishedOriginal passage ↗
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.
- Exponential Time Hypothesis →Open
  A stronger quantitative hypothesis than P ≠ NP.
- P ≠ NP →Open
  The conjectural negative answer to the same canonical question.
Supporting relationship theorem ETH would separate P and NP → Proved
- Impagliazzo–Paturi · On the complexity of k-SAT§1–2, k-SAT exponential complexity and hypothesisPublishedOriginal passage ↗
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.
- Strong Exponential Time Hypothesis — randomized version →Open
  A fine-grained hardness premise stronger than the deterministic version; neither version follows from P ≠ NP.
- P ≠ NP →Open
  The conjectural negative answer to the same canonical question.
Supporting relationship theorem Randomized SETH would separate P and NP → Proved
- Cygan et al. · On problems as hard as CNF-SAT§1 definition; Theorem 1.1(i); immediate consequence using deterministic algorithms as a subclassPreprintOriginal passage ↗
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.
- Avi Wigderson · Mathematics and Computation§12.4, algebraic reductions and completenessPublishedOriginal passage ↗
P = NP
Open
P = NP
The affirmative answer to the canonical question.
P = NP →
SAT in polynomial time
Open
SAT in polynomial time
The SAT decision target; presently unresolved.
SAT in polynomial time →
P ≠ NP
Open
P ≠ NP
The conjectural negative answer to the same canonical question.
P ≠ NP →
NP ⊄ P/poly
Open
NP lacks polynomial-size general circuits
A stronger circuit-complexity target than P ≠ NP.
NP lacks polynomial-size general circuits →
NP ≠ coNP
Open
NP ≠ coNP
A stronger related separation; not equivalent to P ≠ NP.
NP ≠ coNP →
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 →
ETH
Open
Exponential Time Hypothesis
A stronger quantitative hypothesis than P ≠ NP.
Exponential Time Hypothesis →
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 →
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.

Avi Wigderson · Mathematics and Computation§5.2.1, Theorem 5.3PublishedOriginal passage ↗
Avi Wigderson · Mathematics and Computation§3.5, NP versus coNPPublishedOriginal passage ↗
Stephen Cook · The P versus NP problemDefinition 2 and problem statement, pp. 2–3PublishedOriginal passage ↗
Impagliazzo–Paturi · On the complexity of k-SAT§1–2, k-SAT exponential complexity and hypothesisPublishedOriginal passage ↗
Impagliazzo–Paturi · On the complexity of k-SAT§1, definition of s_k and the exponential-time hypothesisPublishedOriginal passage ↗
Stephen Cook · The P versus NP problemProblem statement and discussion, pp. 2–3PublishedOriginal passage ↗
Avi Wigderson · Mathematics and Computation§5.2.1, Theorem 5.3 and Conjecture 5.4PublishedOriginal passage ↗
Stephen Cook · The P versus NP problemProof complexity discussion, pp. 5–6PublishedOriginal passage ↗
Avi Wigderson · Mathematics and ComputationDefinition 4.7 and §4.5PublishedOriginal passage ↗
Avi Wigderson · Mathematics and Computation§4.4–4.5, Definition 4.7 and discussionPublishedOriginal passage ↗
Stephen Cook · The P versus NP problemDefinition 4, Proposition 1(c) and SAT NP-completeness discussion, pp. 4–5PublishedOriginal passage ↗
Stephen Cook · The P versus NP problemProposition 1(c) and SAT NP-completeness discussion, p. 5PublishedOriginal passage ↗
Cygan et al. · On problems as hard as CNF-SAT§1 definition; Theorem 1.1(i); immediate consequence using deterministic algorithms as a subclassPreprintOriginal passage ↗
Cygan et al. · On problems as hard as CNF-SAT§1, Previous Work, p. 1; Theorem 1.1(i)PreprintOriginal passage ↗
Avi Wigderson · Mathematics and Computation§12.4, algebraic reductions and completenessPublishedOriginal passage ↗

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

Equivalent formulations 1

P = NP equivalent to SAT in polynomial time.
Cited equivalence
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.
Sources & review
Relationship statement: SAT captures P versus NPProved
Independent relationship review: not recorded. Link to this connection

Implications 5

NP lacks polynomial-size general circuits implies P ≠ NP.
Cited implication
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.
Sources & review
Relationship statement: General NP circuit lower bounds would separate P and NPProved
Independent relationship review: not recorded. Link to this connection
NP ≠ coNP implies P ≠ NP.
Cited implication
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.
Sources & review
Relationship statement: NP versus coNP would separate P and NPProved
Independent relationship review: not recorded. Link to this connection
Standard one-way functions exist implies P ≠ NP.
Cited implication
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.
Sources & review
Relationship statement: One-way functions would separate P and NPProved
Independent relationship review: not recorded. Link to this connection
Exponential Time Hypothesis implies P ≠ NP.
Cited implication
ETH rules out even subexponential 3SAT algorithms in the stated model.
Limit P ≠ NP does not by itself establish exponential runtime lower bounds.
Sources & review
Relationship statement: ETH would separate P and NPProved
Independent relationship review: not recorded. Link to this connection
Strong Exponential Time Hypothesis — randomized version implies P ≠ NP.
Cited implication
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.
Sources & review
Relationship statement: Randomized SETH would separate P and NPProved
Independent relationship review: not recorded. Link to this connection

Analogues and related questions 1

VP versus VNP analogue of P ≠ NP.
Analogue · different setting
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.
Sources & review
- Avi Wigderson · Mathematics and Computation ↗§12.4, algebraic reductions and completeness
Independent relationship review: not recorded. Link to this connection

Consequences 4

Assuming P = NPOpen

Optimization and witness search
Conditional
If P = NP, polynomially bounded NP witnesses can be found in polynomial time. This applies to suitably encoded search tasks and exact optimization reducible to polynomially many such decision queries.
Limit Output-size and encoding assumptions matter; the existence theorem does not provide a usable implementation or small runtime constants.
- If P = NP, NP witnesses can be found efficientlyProved
Sources & review
Supporting statements
- If P = NP, NP witnesses can be found efficiently →
- Stephen Cook · The P versus NP problem ↗Decision versus search discussion, p. 5
Source-grounded explanation · independent explanation review: pending.
Cryptographic hardness assumptions
Conditional
If P = NP, standard one-way functions cannot exist: their inversion witnesses would become polynomial-time searchable. This changes the asymptotic assumptions supporting computational cryptography.
Limit An equality proof alone does not predict immediate attacks, engineering cost, or the fate of information-theoretic security. P ≠ NP alone does not establish average-case security.
- One-way functions would separate P and NPProved
- If P = NP, NP witnesses can be found efficientlyProved
Sources & review
Supporting statements
- One-way functions would separate P and NP →
- If P = NP, NP witnesses can be found efficiently →
- Avi Wigderson · Mathematics and Computation ↗§4.4–4.5, Definition 4.7 and discussion
- Stephen Cook · The P versus NP problem ↗Decision versus search discussion, p. 5
Source-grounded explanation · independent explanation review: pending.
Several levels of verification collapse
Conditional
If P = NP, the classical polynomial hierarchy collapses to P, connecting nested existential and universal verification tasks to deterministic polynomial time.
Limit This consequence concerns the defined hierarchy; exact counting, arbitrary mathematical truth and practical runtimes are separate questions.
- If P = NP, the polynomial hierarchy collapses to PProved
Sources & review
Supporting statements
- If P = NP, the polynomial hierarchy collapses to P →
- Avi Wigderson · Mathematics and Computation ↗§4.1, polynomial hierarchy; P = NP collapse discussion
Source-grounded explanation · independent explanation review: pending.

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.
- If P ≠ NP, NP-complete problems have no polynomial algorithmProved
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
- Stephen Cook · The P versus NP problem ↗Definition 4 and Proposition 1(c), pp. 4–5
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.

General NP circuit lower bounds would separate P and NP (Proved)
NEXP has no polynomial-size ACC circuits (Proved)
Depth-two threshold circuits require superquadratic size (Proved)

Sources & review

Supporting statements

Avi Wigderson · Mathematics and Computation ↗§5.2.1, Theorem 5.3
Ryan Williams · Non-uniform ACC circuit lower bounds ↗Abstract and main theorem, p. 1
Chen–Tal–Wang · Depth-two threshold lower bounds ↗Theorem 1.1, §1.1.1, p. 2

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.

Relativizing techniques cannot settle P versus NP (Proved)
The natural-proofs barrier is conditional (Proved)
Algebrizing techniques cannot settle P versus NP (Proved)

Sources & review

Supporting statements

Baker–Gill–Solovay · Relativizations of the P =? NP question ↗Original paper abstract, SIAM J. Comput. 4(4), 431–442, DOI 10.1137/0204037
Razborov–Rudich · Natural proofs ↗§2.2 (natural properties), p. 7; hardness definition and Theorem 4.1, p. 15
Aaronson–Wigderson · Algebrization ↗§2 definitions; §5 oracle constructions; introduction pp. 3–4

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.

VP versus VNP (Open)
NP ≠ coNP (Open)

Sources & review

Supporting statements

Avi Wigderson · Mathematics and Computation ↗§12.4, algebraic reductions and completeness
Stephen Cook · The P versus NP problem ↗Proof complexity discussion, pp. 5–6

Source-grounded explanation · independent explanation review: pending.

Timeline

Oct 6, 2026New 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.
- 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
Oct 5, 2026AI-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.
- A truly subquadratic deterministic 3SUM algorithmProved
- A truly subcubic deterministic APSP algorithmProved
- 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
Jul 10, 2026Near-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.
- Near-maximum general circuit lower bound in an oracle classProved
- Ren–Williams · Near-maximum circuit lower bounds ↗Theorem 1.1, p. 2
Mar 15, 2026A 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.
- Depth-two threshold circuits require superquadratic sizeProved
- Chen–Tal–Wang · Depth-two threshold lower bounds ↗Theorem 1.1, §1.1.1, p. 2
2011Algorithms 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.
- NEXP has no polynomial-size ACC circuitsProved
- Ryan Williams · Non-uniform ACC circuit lower bounds ↗Abstract and main theorem, p. 1
2008Algebrization 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.
- Algebrizing techniques cannot settle P versus NPProved
- Aaronson–Wigderson · Algebrization ↗§2 definitions; §5 oracle constructions; introduction pp. 3–4
1994Natural 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.
- The natural-proofs barrier is conditionalProved
- Razborov–Rudich · Natural proofs ↗§2.2 (natural properties), p. 7; hardness definition and Theorem 4.1, p. 15
Dec 1975Oracle 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.
- Relativizing techniques cannot settle P versus NPProved
- Baker–Gill–Solovay · Relativizations of the P =? NP question ↗Original paper abstract, SIAM J. Comput. 4(4), 431–442, DOI 10.1137/0204037
1975Conditional 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.
- If P ≠ NP, intermediate problems existProved
- Avi Wigderson · Mathematics and Computation ↗Theorem 4.1 [Lad75], §4.2
1971NP-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.
- SAT captures P versus NPProved
- Stephen Cook · The P versus NP problem ↗Definition 4, Proposition 1(c) and SAT NP-completeness discussion, pp. 4–5

Full history with sources →

Evidence

Evidence by kind
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

Introduction: P versus NP →

Bibliography 16

Stephen Cook · The P versus NP problem →
Stephen Cook · Published
Clay · Millennium Problems →
Clay Mathematics Institute
Clay · P versus NP →
Clay Mathematics Institute · Project documentation
Avi Wigderson · Mathematics and Computation →
Avi Wigderson · Published · 2019
Baker–Gill–Solovay · Relativizations of the P =? NP question →
Theodore Baker · John Gill · Robert Solovay · Published · Dec 1975
Razborov–Rudich · Natural proofs →
Alexander Razborov · Steven Rudich · Published · 1994
Aaronson–Wigderson · Algebrization →
Scott Aaronson · Avi Wigderson · Published · 2008
Ryan Williams · Non-uniform ACC circuit lower bounds →
Ryan Williams · Published · 2011
Impagliazzo–Paturi · On the complexity of k-SAT →
Russell Impagliazzo · Ramamohan Paturi · Published · Mar 2001
Chen–Tal–Wang · Depth-two threshold lower bounds →
Lijie Chen · Avishay Tal · Yichuan Wang · Preprint · Mar 15, 2026
Ren–Williams · Near-maximum circuit lower bounds →
Hanlin Ren · Ryan Williams · Preprint · Jul 10, 2026
Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP →
Josh Alman · Virginia Vassilevska Williams · Preprint · Oct 5, 2026
OpenAI · Mathematics release: complexity proposals →
OpenAI internal model; author attribution per manuscript · Project documentation · Oct 6, 2026
Robust MDP policy iteration and Aletheia contribution →
Ali Asadi · Krishnendu Chatterjee · Ehsan Goharshady · Mehrdad Karrabi · Alipasha Montaseri · Carlo Pagano · Acceptance reported · 2026
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 · Preprint · Sep 11, 2023
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 · Preprint · Mar 27, 2014

Research activity · 2 entries

Contributions

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.

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 →

Research direction

Dong et al. · Large language model for science: P vs NP

The authors report a GPT-4-produced proposed P ≠ NP proof schema.

This research-workflow report is not an accepted proof, a formal check or a resolution of the canonical assertion.

Related statements · context, not additional proved progress

P ≠ NP →

Dong et al. · Large language model for science: P vs NP · sources & artifacts →

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

Record details

Record version: 9
Classification: MSC2020 68Q15
Prerequisite level: undergraduate

Source observations & version history →

Overview

Known

Open questions

Latest

How to read this question

What would settle this question?

Checking, finding and practical efficiency

Results

The question 2

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Equivalent formulations 2

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Proposed 3

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Conditional implications 10

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Proof barriers 3

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources

Restricted-model lower bounds 3

Assumptions

In this problem

Sources

Assumptions

In this problem

Sources