Math Conjectures

Strong Exponential Time Hypothesis

OPENMajorConjectureProposed 2001 · Standard version

Canonical statement

For every ε>0\varepsilon>0 there exists an integer k≥3k\geq3 such that kk-SAT—satisfiability of CNF formulas whose clauses contain at most kk literals—on nn variables cannot be decided by a deterministic algorithm in time
O((2−ε)n). O((2-\varepsilon)^n).
View source LaTeX
For every \(\varepsilon>0\) there exists an integer
\(k\geq3\) such that \(k\)-SAT—satisfiability of CNF formulas whose
clauses contain at most \(k\) literals—on \(n\) variables cannot be
decided by a
deterministic algorithm in time
\[
  O((2-\varepsilon)^n).
\]
TCS-010:[ImpagliazzoPaturi2001ETH][ImpagliazzoPaturiZane2001][CyganEtAl2015Parameterized]
Theoretical computer scienceOperations research

Notes

The Strong Exponential Time Hypothesis (SETH) concerns satisfiability of CNF formulas whose clauses have width at most kk. It asserts that for every ε>0\varepsilon>0 there is some k≥3k\geq3 for which kk-SAT on nn variables cannot be decided by a deterministic algorithm in time O((2−ε)n)O((2-\varepsilon)^n); equivalently, the best achievable exponential base for kk-SAT tends to 22 as kk grows. The hypothesis was formulated by Impagliazzo and Paturi in 2001 [ImpagliazzoPaturi2001ETH], alongside the companion study of strongly exponential complexity by Impagliazzo, Paturi and Zane [ImpagliazzoPaturiZane2001].

Known algorithms are consistent with the hypothesis: for every fixed kk one can beat exhaustive search, but the bases of these running times approach 22 as kk increases, and no improvement bounded away from 22 uniformly in kk has been found. SETH strictly strengthens the Exponential Time Hypothesis, and both assumptions are used side by side because they support different quantitative lower bounds, notably tight running-time bounds in parameterized complexity [CyganEtAl2015Parameterized].

The hypothesis is open in both directions: refuting it requires a (2−ε)n(2-\varepsilon)^n-time algorithm working for all kk, while proving it would require unconditional lower bounds far beyond current techniques.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.