Résumé |
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.
Joint work with Thomas Dueholm Hansen, Haim Kaplan and Or Zamir |