In 1998, Paturi, Pudl´ak, 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−k)n, where k 2 (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 2(1−k)n, for k 2 O(log2 k/k).
Proceedings of the Annual Acm-siam Symposium on Discrete Algorithms, 2013, p. 1253-1263
Main Research Area:
Annual a C M - S I a M Symposium on Discrete Algorithms. Proceedings
ACM-SIAM symposium on Disrete AlgorithmsSymposium on Discrete Algorithms, 2013