P versus NP · OpenMath

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.

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.
Stephen Cook · The P versus NP problem →

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.

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 assumptions The 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.

If P ≠ NP
Open
P ≠ NP
The conjectural negative answer to the same canonical question.
P ≠ NP →
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 →
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 →
If P = NP
Open
P = NP
The affirmative answer to the canonical question.
P = NP →
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 →
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 →
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.

Stephen Cook · The P versus NP problemDefinition 2 and problem statement, pp. 2–3PublishedOriginal passage ↗
Avi Wigderson · Mathematics and Computation§4.1, polynomial hierarchy; P = NP collapse discussionPublishedOriginal passage ↗
Stephen Cook · The P versus NP problemProblem statement and discussion, pp. 2–3PublishedOriginal passage ↗
Avi Wigderson · Mathematics and ComputationTheorem 4.1 [Lad75], §4.2PublishedOriginal passage ↗
Stephen Cook · The P versus NP problemDefinition 4 and Proposition 1(c), pp. 4–5PublishedOriginal passage ↗
Stephen Cook · The P versus NP problemDecision versus search discussion, p. 5PublishedOriginal passage ↗
Stephen Cook · The P versus NP problemDefinition 4, Proposition 1(c) and SAT NP-completeness discussion, pp. 4–5PublishedOriginal passage ↗

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

E^NP: size n^(2.5−ε) needed● Proved under stated assumptions

E^prMA/1: size Ω(2ⁿ/n) needed● Proved under stated assumptions

Barriers: techniques proved unable to reach the target

Relativization● Proved under stated assumptions Natural proofs● Proved under stated assumptions Algebrization● 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.

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 →
E^NP: 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 →
E^prMA/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 →
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 →
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 →
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 →
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.

Aaronson–Wigderson · Algebrization§2 definitions; §5 oracle constructions; introduction pp. 3–4PublishedOriginal passage ↗
Razborov–Rudich · Natural proofs§2.2 (natural properties), p. 7; hardness definition and Theorem 4.1, p. 15PublishedOriginal passage ↗
Ren–Williams · Near-maximum circuit lower boundsTheorem 1.1, p. 2PreprintOriginal passage ↗
Ryan Williams · Non-uniform ACC circuit lower boundsAbstract and main theorem, p. 1PublishedOriginal passage ↗
Avi Wigderson · Mathematics and Computation§5.2.1, Theorem 5.3 and Conjecture 5.4PublishedOriginal passage ↗
Baker–Gill–Solovay · Relativizations of the P =? NP questionOriginal paper abstract, SIAM J. Comput. 4(4), 431–442, DOI 10.1137/0204037PublishedOriginal passage ↗
Chen–Tal–Wang · Depth-two threshold lower boundsTheorem 1.1, §1.1.1, p. 2PreprintOriginal passage ↗

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

General NP circuit lower bounds 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
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
Randomized Strong Exponential Time Hypothesis 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
Boolean and algebraic complexity. 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
Stephen Cook · The P versus NP problem →
Read the setting and notation before comparing the results.
Proof source
Ryan Williams · Non-uniform ACC circuit lower bounds →
Read the mathematical argument; inspect its statement for assessment and scope.

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

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.

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

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 →

Overview

Known

Open questions

Latest

Definitions

How to read this question

What would settle this question?

Checking, finding and practical efficiency

Landscape

The two possible worlds

If P ≠ NP

If P = NP

P ≠ NP

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

If P ≠ NP, intermediate problems exist

P = NP

If P = NP, NP witnesses can be found efficiently

If P = NP, the polynomial hierarchy collapses to P

SAT captures P versus NP

How far circuit lower bounds reach

NEXP has no polynomial-size ACC circuits

Depth-two threshold circuits require superquadratic size

Near-maximum general circuit lower bound in an oracle class

Relativizing techniques cannot settle P versus NP

The natural-proofs barrier is conditional

Algebrizing techniques cannot settle P versus NP

NP lacks polynomial-size general circuits

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