Definition
Strong Exponential Time Hypothesis
Simplified
For every constant
, SAT cannot be solved in running time, i.e., where
is the number of variables and denotes Big-O-star notation. Every constant below
? SETH conjectures that the coefficient of
in the exponent cannot be reduced below . Hence none of the successive improvements can be achieved for general SAT, apart from polynomial factors.
Exhaustive Branching
For SAT, exhaustive branching with running time
is essentially optimal; the base cannot be improved by any fixed constant amount, i.e., Clause width
For each
, let The strong exponential time hypothesis states that
Equivalently, for every
, there is a clause width for which k-SAT has no algorithm. The width may depend on . SETH forbids smaller linear exponents such as
. It therefore also forbids sublinear exponents such as or .
Relation to ETH
ETH says that 3-SAT has no subexponential-time algorithm of the form
SETH is stronger. It rules out even slightly faster-than-brute-force algorithms for SAT, such as
Thus:
- ETH forbids improving the exponent all the way to sublinear in
; - SETH forbids improving the constant in the exponent below
.
Formal variant
A common formal version is stated through k-SAT: for every
This avoids claiming that every fixed-width SAT variant has exactly the same exponential constant.