Exponential Lower Bounds for PPSZ k-SAT Algorithm

Abstract

In 1998, Paturi, Pudlák, Saks, and Zane presented PPSZ, an elegant randomized algorithm for $k$-SAT. Fourteen years on, this algorithm is still the fastest known worst-case algorithm. They proved that its expected running time on $k$-CNF formulas with $n$ variables is at most $2^{(1 - \epsilon_k)n}$ where $\epsilon_k \in \Omega(1/k)$. In this paper, we construct hard instances for PPSZ. That is, we construct satisfiable $k$-CNF formulas over $n$ variables on which the expected running time is at least $2^{(1 - \epsilon_k)n}$ where $\epsilon_k \in O(\log^2 (k)/k)$.

Publication
Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Date
Links