Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-069 | 15th October 2021 07:32

PPSZ is better than you think

RSS-Feed




Revision #1
Authors: Dominik Scheder
Accepted on: 15th October 2021 07:32
Downloads: 710
Keywords: 


Abstract:

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being implied by a small set of clauses).
We show that PPSZ performs exponentially better than previously known, for all k >= 3. For Unique-3-SAT we bound its running time by O(1.306973n), which is somewhat better than the algorithm of Hansen, Kaplan, Zamir, and Zwick.
All improvements are achieved without changing the original PPSZ. The core idea is to pretend that PPSZ does not process the variables in uniformly random order, but according to a carefully designed distribution. We write "pretend" since this can be done without any actual change to the algorithm.



Changes to previous version:

- Appendix D, "Proofs from Section 8" was missing (I simply forgot some \input{...})
- I removed unused equation numbers


Paper:

TR21-069 | 12th May 2021 06:23

PPSZ is better than you think





TR21-069
Authors: Dominik Scheder
Publication: 12th May 2021 11:47
Downloads: 1503
Keywords: 


Abstract:

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being implied by a small set of clauses).
We show that PPSZ performs exponentially better than previously known, for all k >= 3. For Unique-3-SAT we bound its running time by O(1.306973n), which is somewhat better than the algorithm of Hansen, Kaplan, Zamir, and Zwick.
All improvements are achieved without changing the original PPSZ. The core idea is to pretend that PPSZ does not process the variables in uniformly random order, but according to a carefully designed distribution. We write "pretend" since this can be done without any actual change to the algorithm.



ISSN 1433-8092 | Imprint