Open
Unresolved assertion in the cited scope ↗
Observed Oct 10, 2026
Conjecture · version 2
Exponential Time Hypothesis
Statement
3SAT cannot be decided in deterministic time 2^{o(n)} times a polynomial in the input length, where n is the number of variables.
Assumptions
- Classical deterministic algorithms; finite CNF input; parameter is variables, not encoded bit length.
Scope
A stronger quantitative hypothesis than P ≠ NP.
Evidence
Source reports
Connections
In this problem · publication v12 · Selected context
P versus NP →
Different statement · related variant · Open
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
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 →Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v14
P versus NP →
Different statement · related variant · Open
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
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 →Relationship not independently reviewed. This concerns its use in this problem.
Sources
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.
Impagliazzo–Paturi · On the complexity of k-SAT — proof text ↗Manuscript / exposition · external
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.
Impagliazzo–Paturi · On the complexity of k-SAT — proof text: JCSS-2001. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
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.
Stephen Cook · Published
Published author exposition or original paper.
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.
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-eth
- Statement version
- 2
- SHA-256
- 8f7c5b6cbec1882302c450e1977162f3ff9ac86d863a89876706dd965beb8e9b