ETH is Dead, Long Live SH
MIT Hardness Group, Josh Brunner, Erik D. Demaine, Fabian Frei, Timothy Gomez, Markus Hecher, Jeffery Li, Jayson Lynch
原文摘要
Among the recent flood of AI-based mathematical breakthroughs (the "mathpocalypse"), perhaps the biggest bombshells in theoretical computer science were two disproofs of the Exponential Time Hypothesis (ETH), via slightly subexponential algorithms for the classic $k$-Satisfiability problems. After the initial shock, the community quickly began to wonder at the implications: how do the hundreds if not thousands of ETH-based lower bounds in the literature need to change? It turns out, not much -- if we are willing to change the exponents ever so slightly. While Impagliazzo and Paturi's 1999 Exponential Time Hypothesis (ETH) is false, 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}})$-time 3SAT algorithms for every constant $\varepsilon>0$, where $n$ is the number of variables. 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$ (the number of variables plus clauses) 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 a running time of $O(2^{k^{1/b-\varepsilon}})L^{O(1)}$ when the reduction produces an instance of length $L$ with parameter $k\le s^{b+o(1)}$. We also prove equivalence of the analogous counting hypotheses, #SH and Weak ETH, and that they rule out $O(2^{s^{1-\varepsilon}})$-time algorithms for #2SAT formulas of size $s$ for every constant $\varepsilon>0$.
cs.CC