3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

2011/03/10 by Timon Hertli, Hertli, Timon · 4 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.1 #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1103.2165

openalex publication_date 2011/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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ⁿ).

Citations

• The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs

Cited by

• A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
• On the Secret Protection Problem in Discrete-Event Systems
• On the optimality of approximation schemes for the classical scheduling problem
• A Casual Tour Around a Circuit Complexity Bound

Related

• Breaking the PPSZ Barrier for Unique 3-SAT
• Improving PPSZ for 3-SAT using Critical Variables
• Simpler Partial Derandomization of PPSZ for k-SAT
• An Improved Algorithm for Sparse Instances of SAT
• An Improved Upper Bound for SAT