Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with NP-complete problems:
TR18-179 | 31st October 2018
Dominik Scheder

PPSZ on CSP Instances with Multiple Solutions

We study the success probability of the PPSZ algorithm on $(d,k)$-CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.

more >>>

TR21-069 | 12th May 2021
Dominik Scheder

PPSZ is better than you think

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint