Exponential Lower Bounds for the PPSZ k-SAT Algorithm
Shiteng Chen, Dominik Scheder, Navid Talebanfard, Bangsheng Tang · 2013
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 , where εk ∊ Ω(1/k). So far, no exponential lower bounds at all have been known. 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 , for εk ∊ O(log2 k/k).