Satisfiability hypothesis stays plausible despite exponential time hypothesis loss
ETH is Dead, Long Live SH
Computational Complexity
Summary
The paper shows that a popular assumption called the Exponential Time Hypothesis (ETH), which suggested certain hard problems can’t be solved quickly, is actually false. However, an older assumption known as the Satisfiability Hypothesis (SH) still seems reasonable. The authors prove that SH is essentially the same as a more recent version called the Weak ETH, which rules out certain fast algorithms for solving 3SAT problems. They also extend these ideas to counting problems, showing similar limitations for counting solutions to logical formulas.
What this means in practice
- •For algorithm designers: Avoid pursuit of algorithms for 3SAT that beat the time limits implied by the Satisfiability Hypothesis, guiding realistic performance expectations.
- •For complexity engineers: Use the equivalence of SH and Weak ETH to justify hardness assumptions when establishing running time lower bounds in parameterized problems.
A theory result. No direct application yet.
Authors
MIT Hardness Group, Josh Brunner, Erik D. Demaine, Fabian Frei, Timothy Gomez, Markus Hecher, Jeffery Li, Jayson Lynch
Abstract
Impagliazzo and Paturi's 1999 Exponential Time Hypothesis (ETH) is false, but Stearns and Hunt's 1990 Satisfiability Hypothesis (SH) remains plausible. We prove that SH is equivalent to the recently proposed Weak ETH which rules out $O(2^{n^{1-\varepsilon}})L^{O(1)}$-time 3SAT algorithms for every constant $\varepsilon>0$, where $L$ is the input length. We show that SH (or Weak ETH) preserves the typical process for lower bounds: a polynomial-time reduction from a 3SAT formula of size $s=Θ(n+m)$ to an instance of size $N\le s^{b+o(1)}$, for fixed blowup exponent $b>0$, rules out $O(2^{N^{1/b-\varepsilon}})$-time algorithms for every constant $\varepsilon>0$. By comparison, for an $N=O(s^b)$ blowup, ETH would have ruled out $2^{o(N^{1/b})}$-time algorithms. The framework also yields parameterized lower bounds ruling out running times of the form $O(2^{k^{1/b-\varepsilon}})L^{O(1)}$. We also prove equivalence of the analogous counting hypotheses, #SH and Weak #ETH, and that they rule out $O(2^{(n+m)^{1-\varepsilon}})$-time algorithms for #2SAT for every constant $\varepsilon>0$.