Open
Unresolved assertion in the cited scope ↗
Stephen Cook · The P versus NP problem · Problem statement and discussion, pp. 2–3 →
Observed Oct 10, 2026
Conjecture · version 3
P ≠ NP
Statement
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
Assumptions
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope
The conjectural negative answer to the same canonical question.
Evidence
Source reports
Connections
In this problem · publication v13 · Selected context
P versus NP →
Alternative answer · Open
Equality and inequality are competing answers to one question, not separate canonical Problems.
Separation is the alternative answer to the same P versus NP question.
One-way implication
Nonuniform general NP circuit lower bounds would suffice for P ≠ NP.
The reverse implication is not established; restricted gates or larger target classes do not satisfy this premise.
Details & sources
NP lacks polynomial-size general circuits →
Open · version 2
NP is not contained in P/poly.
- Nonuniform families of polynomial-size unrestricted Boolean circuits.
Scope: A stronger circuit-complexity target than P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
General NP circuit lower bounds would separate P and NP →
Relationship statement · Proved · version 2
If NP is not contained in P/poly, then P ≠ NP.
- Uniform polynomial-time algorithms have polynomial-size nonuniform circuits.
Scope: A one-direction sufficient condition; the converse is not established.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
implies ↓This statement: P ≠ NP
Separating NP from coNP would also separate P from NP.
The converse is not established; short proofs in one particular proof system are a narrower question.
Details & sources
NP ≠ coNP →
Open · version 2
NP and coNP are distinct.
- Classical NP and complements of NP languages.
Scope: A stronger related separation; not equivalent to P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
NP versus coNP would separate P and NP →
Relationship statement · Proved · version 2
If NP ≠ coNP, then P ≠ NP.
- P is closed under complementation.
Scope: The implication does not establish its premise.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
Average-case one-wayness is a stronger sufficient hardness premise.
P ≠ NP alone does not establish one-way functions or the security of a particular cryptosystem.
Details & sources
Standard one-way functions exist →
Open · version 2
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
- The standard asymptotic cryptographic definition, efficient sampling and polynomially bounded encodings.
Scope: Average-case cryptographic hardness; stronger than merely worst-case NP hardness.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
One-way functions would separate P and NP →
Relationship statement · Proved · version 2
If standard one-way functions exist, then P ≠ NP.
- Standard polynomially bounded one-way functions; classical polynomial-time computation.
Scope: The reverse implication is not established; P ≠ NP alone is not a security guarantee.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
ETH rules out even subexponential 3SAT algorithms in the stated model.
P ≠ NP does not by itself establish exponential runtime lower bounds.
Details & sources
Exponential Time Hypothesis →
Open · version 2
3SAT cannot be decided in deterministic time 2^{o(n)} times a polynomial in the input length, where n is the number of variables.
- Classical deterministic algorithms; finite CNF input; parameter is variables, not encoded bit length.
Scope: A stronger quantitative hypothesis than P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
ETH would separate P and NP →
Relationship statement · Proved · version 2
If ETH holds, then P ≠ NP.
- ETH in the stated variable-parameter deterministic model; 3SAT is NP-complete.
Scope: A sufficient stronger hardness hypothesis; P ≠ NP does not establish ETH.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
The cited randomized SETH excludes even fixed-base exponential improvements for some clause width, and therefore excludes polynomial deterministic algorithms.
This version is stronger than deterministic SETH; neither is implied by P ≠ NP.
Details & sources
Strong Exponential Time Hypothesis — randomized version →
Open · version 2
For every fixed α in (0,1), there is a fixed clause width k such that k-CNF-SAT on n variables has no bounded-error randomized O(2^{αn})-time algorithm.
- The bounded-error randomized convention explicitly used in Cygan et al., §1; width k depends on α.
- Parameter is the number of variables; fixed-width formulas can be normalized to polynomial input length.
Scope: A fine-grained hardness premise stronger than the deterministic version; neither version follows from P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
Randomized SETH would separate P and NP →
Relationship statement · Proved · version 2
If the stated bounded-error randomized SETH holds, then P ≠ NP.
- The stated SETH formulation; deterministic algorithms are a special case of bounded-error randomized algorithms; fixed-width SAT is in NP.
Scope: Only a sufficient stronger premise; P ≠ NP gives no such exponent or randomized lower bound.
Relationship not independently reviewed.
Connection in P versus NP →Analogue
analogous toThis statement: P ≠ NP
VP versus VNP is an algebraic complexity analogue, with field operations and polynomial families.
No equivalence or implication to the classical Boolean question is asserted.
Details & sources
VP versus VNP →
Open · version 2
Over a field of characteristic zero, VP and VNP are distinct.
- Polynomial families with polynomially bounded degree; nonuniform algebraic circuits; arithmetic operation complexity over the field.
Scope: An algebraic analogue; no equivalence to Boolean P versus NP is asserted.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v14
P versus NP →
Alternative answer · Open
Equality and inequality are competing answers to one question, not separate canonical Problems.
Separation is the alternative answer to the same P versus NP question.
One-way implication
Nonuniform general NP circuit lower bounds would suffice for P ≠ NP.
The reverse implication is not established; restricted gates or larger target classes do not satisfy this premise.
Details & sources
NP lacks polynomial-size general circuits →
Open · version 2
NP is not contained in P/poly.
- Nonuniform families of polynomial-size unrestricted Boolean circuits.
Scope: A stronger circuit-complexity target than P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
General NP circuit lower bounds would separate P and NP →
Relationship statement · Proved · version 2
If NP is not contained in P/poly, then P ≠ NP.
- Uniform polynomial-time algorithms have polynomial-size nonuniform circuits.
Scope: A one-direction sufficient condition; the converse is not established.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
implies ↓This statement: P ≠ NP
Separating NP from coNP would also separate P from NP.
The converse is not established; short proofs in one particular proof system are a narrower question.
Details & sources
NP ≠ coNP →
Open · version 2
NP and coNP are distinct.
- Classical NP and complements of NP languages.
Scope: A stronger related separation; not equivalent to P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
NP versus coNP would separate P and NP →
Relationship statement · Proved · version 2
If NP ≠ coNP, then P ≠ NP.
- P is closed under complementation.
Scope: The implication does not establish its premise.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
Average-case one-wayness is a stronger sufficient hardness premise.
P ≠ NP alone does not establish one-way functions or the security of a particular cryptosystem.
Details & sources
Standard one-way functions exist →
Open · version 2
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
- The standard asymptotic cryptographic definition, efficient sampling and polynomially bounded encodings.
Scope: Average-case cryptographic hardness; stronger than merely worst-case NP hardness.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
One-way functions would separate P and NP →
Relationship statement · Proved · version 2
If standard one-way functions exist, then P ≠ NP.
- Standard polynomially bounded one-way functions; classical polynomial-time computation.
Scope: The reverse implication is not established; P ≠ NP alone is not a security guarantee.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
ETH rules out even subexponential 3SAT algorithms in the stated model.
P ≠ NP does not by itself establish exponential runtime lower bounds.
Details & sources
Exponential Time Hypothesis →
Open · version 2
3SAT cannot be decided in deterministic time 2^{o(n)} times a polynomial in the input length, where n is the number of variables.
- Classical deterministic algorithms; finite CNF input; parameter is variables, not encoded bit length.
Scope: A stronger quantitative hypothesis than P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
ETH would separate P and NP →
Relationship statement · Proved · version 2
If ETH holds, then P ≠ NP.
- ETH in the stated variable-parameter deterministic model; 3SAT is NP-complete.
Scope: A sufficient stronger hardness hypothesis; P ≠ NP does not establish ETH.
Relationship not independently reviewed.
Connection in P versus NP →One-way implication
The cited randomized SETH excludes even fixed-base exponential improvements for some clause width, and therefore excludes polynomial deterministic algorithms.
This version is stronger than deterministic SETH; neither is implied by P ≠ NP.
Details & sources
Strong Exponential Time Hypothesis — randomized version →
Open · version 2
For every fixed α in (0,1), there is a fixed clause width k such that k-CNF-SAT on n variables has no bounded-error randomized O(2^{αn})-time algorithm.
- The bounded-error randomized convention explicitly used in Cygan et al., §1; width k depends on α.
- Parameter is the number of variables; fixed-width formulas can be normalized to polynomial input length.
Scope: A fine-grained hardness premise stronger than the deterministic version; neither version follows from P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
Randomized SETH would separate P and NP →
Relationship statement · Proved · version 2
If the stated bounded-error randomized SETH holds, then P ≠ NP.
- The stated SETH formulation; deterministic algorithms are a special case of bounded-error randomized algorithms; fixed-width SAT is in NP.
Scope: Only a sufficient stronger premise; P ≠ NP gives no such exponent or randomized lower bound.
Relationship not independently reviewed.
Connection in P versus NP →Analogue
analogous toThis statement: P ≠ NP
VP versus VNP is an algebraic complexity analogue, with field operations and polynomial families.
No equivalence or implication to the classical Boolean question is asserted.
Details & sources
VP versus VNP →
Open · version 2
Over a field of characteristic zero, VP and VNP are distinct.
- Polynomial families with polynomially bounded degree; nonuniform algebraic circuits; arithmetic operation complexity over the field.
Scope: An algebraic analogue; no equivalence to Boolean P versus NP is asserted.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
Sources
Stephen Cook · The P versus NP problem →
- Problem statement and discussion, pp. 2–3 → · Original passage ↗
Recorded wording
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- Proof complexity discussion, pp. 5–6 → · Original passage ↗
Recorded wording
NP and coNP are distinct.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Stephen Cook · Published
Published author exposition or original paper.
Stephen Cook · The P versus NP problem — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: official-description-sha256-018f3d473d16. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Stephen Cook · The P versus NP problem — proof text: official-description-sha256-018f3d473d16. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Avi Wigderson · Mathematics and Computation →
- §5.2.1, Theorem 5.3 and Conjecture 5.4 → · Original passage ↗
Recorded wording
NP is not contained in P/poly.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §5.2.1, Theorem 5.3 → · Original passage ↗
Recorded wording
If NP is not contained in P/poly, then P ≠ NP.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §3.5, NP versus coNP → · Original passage ↗
Recorded wording
If NP ≠ coNP, then P ≠ NP.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- Definition 4.7 and §4.5 → · Original passage ↗
Recorded wording
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §4.4–4.5, Definition 4.7 and discussion → · Original passage ↗
Recorded wording
If standard one-way functions exist, then P ≠ NP.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §12.4, algebraic reductions and completeness → · Original passage ↗
Recorded wording
Over a field of characteristic zero, VP and VNP are distinct.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Avi Wigderson · Published · Publication date 2019
Published author exposition or original paper.
Revision & attribution
Source revision: author-draft-2019-08-06. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Impagliazzo–Paturi · On the complexity of k-SAT →
- §1, definition of s_k and the exponential-time hypothesis → · Original passage ↗
Recorded wording
3SAT cannot be decided in deterministic time 2^{o(n)} times a polynomial in the input length, where n is the number of variables.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §1–2, k-SAT exponential complexity and hypothesis → · Original passage ↗
Recorded wording
If ETH holds, then P ≠ NP.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Russell Impagliazzo · Ramamohan Paturi · Published · Publication date Mar 2001
Published author exposition or original paper.
Revision & attribution
Source revision: JCSS-2001. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Cygan et al. · On problems as hard as CNF-SAT →
- §1, Previous Work, p. 1; Theorem 1.1(i) → · Original passage ↗
Recorded wording
For every fixed α in (0,1), there is a fixed clause width k such that k-CNF-SAT on n variables has no bounded-error randomized O(2^{αn})-time algorithm.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §1 definition; Theorem 1.1(i); immediate consequence using deterministic algorithms as a subclass → · Original passage ↗
Recorded wording
If the stated bounded-error randomized SETH holds, then P ≠ NP.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Marek Cygan · Holger Dell · Daniel Lokshtanov · Dániel Marx · Jesper Nederlof · Yoshio Okamoto · Ramamohan Paturi · Saket Saurabh · Magnus Wahlström · Preprint · Publication date Mar 27, 2014
Author full version dated March 2014; an extended abstract appeared at CCC 2012. The paper explicitly uses a bounded-error randomized formulation of SETH.
Revision & attribution
Source revision: arXiv-1112.2275v3. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Open
Unresolved assertion in the cited scope ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-inequality
- Statement version
- 3
- SHA-256
- e3c33603bd67787399a6837a5997ced659050ea38d7743545cdf081f43f545ac