Exponential Time Hypothesis

Definition

Exponential Time Hypothesis

Simplified

The exists a constant such that 3-SAT cannot be solved in running time, i.e.,

where denotes the Big-O-star notation.

Some with no such algorithm?

ETH says there s some fixed such that 3-SAT algorithm runs in

So you can imagine trying to improve the exponent coefficient:

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

Subexponential

Equivalently, 3-SAT cannot be solved in running time. In other words, there is no algorithm with subexponential running time.

Why is this equivalent?

Recall that

Hence, for every fixed ,

for sufficiently large .

Therefore, if ETH gives us some fixed below which no algorithm eixsts, then every exponent would eventually fall below as well.

Thus ETH rules out every subexponential running time .

ETH forbids exponents that are sublinear in , such as or . It does not forbid every improvement over brute force; an algorithm with running time would still be compatible with ETH.

Equivalent forms

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

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 .

SETH is stronger than ETH: it rules out SAT algorithms with running time for constants , 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.