Open
Unresolved assertion in the cited scope ↗
Cygan et al. · On problems as hard as CNF-SAT · §1, Previous Work, p. 1; Theorem 1.1(i) →
Observed Oct 10, 2026
Conjecture · version 1
Strong Exponential Time Hypothesis — randomized version
Earlier version 1. View current version 2 →
Statement
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.
Assumptions
- 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.
Evidence
Source reports
Connections
In this problem · publication v7
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
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 1
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 2
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 1
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 →Relationship not independently reviewed. This concerns its use in this problem.
Sources
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.
Cygan et al. · On problems as hard as CNF-SAT — proof text ↗Manuscript / exposition · external
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.
Cygan et al. · On problems as hard as CNF-SAT — proof text: arXiv-1112.2275v3. 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-seth
- Statement version
- 1
- SHA-256
- 8039bf1e9050ece1c9188c1f4f21a9c553f7145ea391abcfe2e4d1b1360416c4