Strong Exponential Time Hypothesis

computation complexity

Definition

Strong Exponential Time Hypothesis

Simplified

For every constant $0<c<1$, SAT cannot be solved in $O^{\ast }(2^{cn})$ running time, i.e.,

$$\forall c\in (0,1):\nexists \text{ algorithm }{\mathcal{A}}_{\mathrm{SAT}}\text{ such that }{T}_{\mathcal{A}}(n)\in O^{\ast }(2^{cn}),$$

where $n$ is the number of variables and $O^{\ast }$ denotes Big-O-star notation.

Every constant below $1$?

SETH conjectures that the coefficient of $n$ in the exponent cannot be reduced below $1$. Hence none of the successive improvements

$$2^n\to 2^{0.99n}\to 2^{0.8n}\to 2^{0.3n}\to \dots$$

can be achieved for general SAT, apart from polynomial factors.

Exhaustive Branching

For SAT, exhaustive branching with running time $O^{\ast }(2^n)$ is essentially optimal; the base $2$ cannot be improved by any fixed constant amount, i.e.,

$$\forall \epsilon >0:\nexists \text{ algorithm with running time}{O}^{\ast }((2-\epsilon {)}^n).$$

Clause width

For each $k\ge 3$, let

$$s_k=\inf \left\{c>0|\exists \text{ algorithm }{\mathcal{A}}_{k\text{-SAT}}\text{ such that }{T}_{\mathcal{A}}(n)\in O^{\ast }(2^{cn})\right\}.$$

The strong exponential time hypothesis states that

$$\underset{k\to \infty }{\lim }{s}_k=1.$$

Equivalently, for every $0<c<1$, there is a clause width $k$ for which k-SAT has no $O^{\ast }(2^{cn})$ algorithm. The width $k$ may depend on $c$.

SETH forbids smaller linear exponents such as $0.99n$. It therefore also forbids sublinear exponents such as $n^{0.9}$ or $\sqrt{n}$.

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.