Paper Info
Title
PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster.
Abstract
The currently fastest known algorithm for k-SAT is PPSZ named after its inventors Paturi, Pudlak, Saks, and Zane [7]. Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify Hertli's 2011 analysis [1] for input formulas with multiple satisfying assignments. Second, we show a "translation result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. Combining this with a result by Hertli from 2014 [2], in which he gives an algorithm for Unique-3-SAT slightly beating PPSZ, we obtain an algorithm beating PPSZ for general 3-SAT, thus obtaining the so far best known worst-case bounds for 3-SAT.
Year
DOI
Venue
2017
10.4230/LIPIcs.CCC.2017.9
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
Boolean satisfiability,exponential algorithms,randomized algorithms
Conference
79
ISSN
Citations 
PageRank 
1868-8969
1
0.37
References 
Authors
0
2
Name
Order
Citations
PageRank
Dominik Scheder18513.54
John P. Steinberger232918.30