Exponential Time Hypothesis

computation complexity

Definition

Exponential Time Hypothesis

The exponential time hypothesis states that 3-SAT cannot be solved in subexponential time in the number of variables $n$.

Equivalently, there is no algorithm for 3-SAT with running time

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

where $n$ is the number of variables and O-star notation suppresses polynomial factors.

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\ne NP$;
• if $P\ne 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.