Super Strong ETH is False for Random \(k\)-SAT

Abstract

It has been hypothesized that \(k\)-SAT is hard to solve for randomly chosen instances near the "critical threshold", where the clause-to-variable ratio is \(2^k \ln 2-\theta(1)\). Feige's hypothesis for \(k\)-SAT says that for all sufficiently large clause-to-variable ratios, random \(k\)-SAT cannot be refuted in polynomial time. It has also been hypothesized that the worst-case \(k\)-SAT problem cannot be solved in \(2^{n(1-\omega_k(1)/k)}\) time, as multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield an \(2^{n(1-1/O(k))}\) time algorithm. This hypothesis has been called the "Super-Strong ETH", modeled after the ETH and the Strong ETH. Our main result is a randomized algorithm which refutes the Super-Strong ETH for the case of random \(k\)-SAT, for any clause-to-variable ratio. Given any random \(k\)-SAT instance \(F\) with \(n\) variables and \(m\) clauses, our algorithm decides satisfiability for \(F\) in \(2^{n(1-\Omega(\log k)/k)}\) time, with high probability. It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1998).