Strong Exponential Time Hypothesis: no (2−ε)ⁿ-time algorithm for k-SAT as k → ∞
Difficulty 88: proving SETH would imply P ≠ NP, so the proof direction is at least as hard as the anchor, and 25 years of attempts at a refutation have failed; it sits just below the Millennium-level problems only because a refutation by a clever SAT algorithm is a live possibility. Application value 21: like UGC (16) it mainly guides algorithm designers, though a refutation would at least give faster exponential-time algorithms. Leverage 81: hundreds of fine-grained lower bounds rest on it, more than on UGC (79) and second in complexity theory only to P vs NP.
The problem
The belief that for logic puzzles with long clauses, trying nearly all settings is essentially the best you can do.
- 1Brute force tries 2ⁿ settings
- 2No big shortcut found in decades
- 3SETH: none exists for long rules
- 4Faster text comparison would break it
- 5So those speeds look unbeatable
Statement. For let be the infimum of numbers such that -SAT on variables can be solved in time (randomised algorithms allowed). SETH says . Equivalently: for every there is a such that -SAT cannot be solved in time .
Built from
earlier problems → this oneThe problems this one is built from: progress or tools it needs (builds on), special cases that come first (generalizes), and weaker results on the way (implies). On the right, what builds on it.
- Start with
- P versus NP: does Boolean satisfiability have a polynomial-time algorithm?Complexity Theory · D100
- Step 2
- Strong Exponential Time Hypothesis: no (2−ε)ⁿ-time algorithm for k-SAT as k → ∞This problem
- Then
- Edit distance: a (1+ε)-approximation in truly subquadratic time n^(2−δ)Complexity Theory · D51
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Fast matrix multiplicationAlgorithm
- Step 4
- Then
- Strong Exponential Time Hypothesis: no (2−ε)ⁿ-time algorithm for k-SAT as k → ∞The problem
State of the art
The best known -SAT algorithms (PPSZ and its refinements) run in time for a constant , consistent with SETH; for CNF-SAT with variables and clauses the best savings are about . Since the 2010s SETH has been one of the main assumptions of fine-grained complexity. Williams (2005) showed that Orthogonal Vectors in truly subquadratic time would refute SETH. Backurs and Indyk (arXiv December 2014; STOC 2015) showed the same for edit distance in time, and Abboud, Backurs and Vassilevska Williams (2015) and Bringmann and Künnemann (2015) for longest common subsequence. Abboud, Hansen, Vassilevska Williams and Williams (2016) derived the edit-distance and LCS bounds from much weaker hypotheses about branching programs. On the limits of SETH-based hardness, Carmosino, Gao, Impagliazzo, Mihajlin, Paturi and Schneider (2016) showed that if the nondeterministic variant NSETH holds, there are no deterministic fine-grained reductions from SAT to 3SUM or APSP. As of October 2026 SETH is neither proved nor refuted. A preprint by Alman and Vassilevska Williams (arXiv:2610.06783, 5 October 2026, unrefereed) gives truly subquadratic 3SUM and truly subcubic APSP algorithms, refuting the 3SUM and APSP hypotheses; the authors list SETH and Orthogonal Vectors as unaffected.
Realistic applications
SETH-based lower bounds tell algorithm designers where not to look: for example, that a truly subquadratic exact edit-distance algorithm, which would be valuable for genome comparison, is unlikely. Refuting SETH would require a algorithm for SAT of unbounded clause width and would yield faster exact algorithms for Orthogonal Vectors and related problems in theory, but the expected practical impact on SAT solving is small because practical solvers exploit structure rather than worst-case exponents.
What counts as solved
A refutation accepted by experts: an algorithm and that solve -SAT in time for every , or a truly subquadratic algorithm for a problem known to be SETH-hard via a fine-grained reduction (for example Orthogonal Vectors or edit distance). A proof of SETH would also resolve it but is far beyond current techniques, since it would imply .
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
A refutation is an algorithm with a running-time analysis, and a proof of SETH would imply P != NP, so neither can be machine-checked today: Mathlib has no fine-grained running-time framework. Experts judge the algorithm and its analysis. A benchmark can show practical speed but cannot settle an asymptotic claim.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Proving SETH is harder than proving P ≠ NP, and refuting it needs a new SAT algorithm paradigm. Both are theory problems; compute serves only experiments with algorithm variants.
Bottlenecks
ranked by votes- #1TheoryProving SETH subsumes P ≠ NP
SETH implies ETH, which implies , so a proof inherits all the P vs NP barriers plus a fine-grained exponent. A proof is not realistic before major lower-bound advances.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Oct 5, 20263SUM and APSP hypotheses refuted in a preprint; SETH unaffectedsource
Alman and Vassilevska Williams posted O(n^1.9992) 3SUM and O(n^2.9995) APSP algorithms for polynomially bounded integers; the paper states that SETH and Orthogonal Vectors are unaffected. Not yet refereed.
- Jan 28, 2015LCS is SETH-hardsource
Abboud, Backurs and Vassilevska Williams showed that truly subquadratic longest common subsequence would refute SETH.
- Dec 1, 2014Edit distance is SETH-hardsource
Backurs and Indyk proved that strongly subquadratic edit distance would refute SETH (arXiv December 2014; STOC 2015).
- Jan 1, 2001ETH, SETH and sparsificationsource
Impagliazzo, Paturi and Zane published the sparsification lemma and the ETH framework in JCSS 2001 (conference versions 1998–99; month not given here).