Faster k -SAT algorithms using biased-PPSZ

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k -SAT problem, for every k >3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k ≥ 3. For k =3 we also improve on Herli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308 n to 1.307 n .

Authors

• Thomas Dueholm Hansen
• Haim Kaplan
• Or Zamir
• Uri Zwick

Keywords

• randomized algorithm
• satisfiability