2026-07-20T05:39:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7535 2024-03-06T10:40:11Z ddc:004 open_access

PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster Scheder, Dominik Steinberger, John P. Boolean satisfiability exponential algorithms randomized algorithms The currently fastest known algorithm for k-SAT is PPSZ named after its inventors Paturi, Pudlak, Saks, and Zane. 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 analysis 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, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dominik Scheder and John P. Steinberger 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.9 urn:nbn:de:0030-drops-75355 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.9 eng https://creativecommons.org/licenses/by/3.0/legalcode