2011 · 36 citations · 5 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityConstraint SatisfactionBoolean SatisfiabilityBoolean Satisfiability ProblemComplexity Of SatisfiabilitySatisfiability
The PPSZ algorithm by Paturi, Pudlák, Saks, and Zane [1998] is the fastest known algorithm for Unique k-SAT, where the input formula does not have more than one satisfying assignment. For k≥5 the same bounds hold for general k-SAT. We show that this is also the case for k=3,4, using a slightly modified PPSZ algorithm. We do the analysis by defining a cost for satisfiable CNF formulas, which we prove to decrease in each PPSZ step by a certain amount. This improves our previous best bounds with Moser and Scheder [2011] for 3-SAT to O(1.308") and for 4-SAT to O(1.469").
5
A probabilistic algorithm for k-SAT and constraint satisfaction problems
T. Schoning · 2003 · 440 citations
An improved exponential-time algorithm for <i>k</i> -SAT
Ramamohan Paturi, Pavel Pudlák, Michael Saks et al. · Journal of the ACM · 2005 · 216 citations
A full derandomization of schöning's k-SAT algorithm
Robin A. Moser, Dominik Scheder · 2011 · 49 citations · Full text