Strong Exponential Time Hypothesis

computation complexity

Definition

Strong Exponential Time Hypothesis

The strong exponential time hypothesis states, in a simplified form, that SAT cannot be solved in time

$$O^{\ast }(2^{cn})$$

for any constant $c<1$, where $n$ is the number of variables and O-star notation suppresses polynomial factors.

Equivalently, the best possible exponential base for general SAT is conjectured to be $2^n$ up to lower-order and polynomial factors.

SETH therefore forbids smaller linear exponents, such as $0.99n$. This is stronger than merely forbidding sublinear exponents such as $n^{0.9}$.

Relation to ETH

ETH says that 3-SAT has no subexponential-time algorithm of the form $O^{\ast }(2^{o(n)})$.

SETH is stronger. It rules out even slightly faster-than-brute-force algorithms for SAT, such as

$$O^{\ast }(2^{0.99n}).$$

Thus:

• ETH forbids improving the exponent all the way to sublinear in $n$;
• SETH forbids improving the constant in the exponent below $1$.

Formal variant

A common formal version is stated through k-SAT: for every $\beta <1$, there exists a clause width $k$ such that $k$-SAT cannot be solved in time $O^{\ast }(2^{\beta n})$.

This avoids claiming that every fixed-width SAT variant has exactly the same exponential constant.