Exponential Time Hypothesis

Definition

Exponential Time Hypothesis

Simplified

The exists a constant $c$ such that 3-SAT cannot be solved in $O^{\ast }(2^{cn})$ running time, i.e.,

$$\exists c>0:\nexists \text{algorithm}{\mathcal{A}}_{\text{3-SAT}}\text{such that}{T}_{\mathcal{A}}(n)\in O^{\ast }(2^{cn}),$$

where $O^{\ast }$ denotes the Big-O-star notation.

Some $c$ with no such algorithm?

ETH says there s some fixed $c_0>0$ such that 3-SAT algorithm runs in

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

So you can imagine trying to improve the exponent coefficient:

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

ETH says this process canot push the coefficient all the way toward 0. There is some positive floor $c_0$.

Subexponential

Equivalently, 3-SAT cannot be solved in $O^{\ast }(2^{o(n)})$ running time. In other words, there is no algorithm with subexponential running time.

Why is this equivalent?

Recall that

$$f(n)=o(n)⟺\underset{n\to \infty }{\lim }\frac{f(n)}{n}=0.$$

Hence, for every fixed $c>0$,

$$f(n)<cn$$

for sufficiently large $n$.

Therefore, if ETH gives us some fixed $c_0>0$ below which no $O^{\ast }(2^{c_{0}n})$ algorithm eixsts, then every $o(n)$ exponent would eventually fall below $c_{0}n$ as well.

Thus ETH rules out every subexponential running time $O^{\ast }(2^{o(n)})$.

ETH forbids exponents that are sublinear in $n$, such as $n^{0.9}$ or $\sqrt{n}$. It does not forbid every improvement over brute force; an algorithm with running time $O^{\ast }(2^{0.99n})$ would still be compatible with ETH.

Equivalent forms

Let $n$ be the number of variables and $m$ the number of clauses of a 3-SAT instance. The following formulations are equivalent up to the standard sparsification results for 3-SAT:

$$O^{\ast }(2^{o(n)}),O^{\ast }(2^{o(m)}),O^{\ast }(2^{o(n+m)}).$$

Thus ETH can be stated using variables, clauses, or total formula size.

Strength

ETH is stronger than P versus NP in the following sense:

• if ETH is true, then 3-SAT has no polynomial-time algorithm, so P ≠ NP;
• if P ≠ NP, ETH may still be false, because 3-SAT might have a non-polynomial but subexponential algorithm such as $2^{O(n^{0.9})}$.

SETH is stronger than ETH: it rules out SAT algorithms with running time $O^{\ast }(2^{cn})$ for constants $c<1$, not only subexponential algorithms.

Use

ETH is used to prove conditional lower bounds for exact algorithms. A typical proof reduces 3-SAT to another problem while controlling the parameter size. If the target problem had a subexponential algorithm, then 3-SAT would also have one, contradicting ETH.