PPSZ for General k-SAT and CSP—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 et al. in J ACM 52(3):337-364, 2005. http://dx.doi.org/10.1145/1066100.1066101 ). 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 the analysis of Hertli (in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science-FOCS 2011, Los Alamitos, 2011) for input formulas with multiple satisfying assignments. Second, we show a “lifting 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. In combination this with results by Hansen et al. (in Charikar and Cohen (ed) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019) and Scheder (in 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021), who all prove improved time bounds for Unique- k -SAT, this gives improved bounds for general k -SAT. We also generalize our results to the domain of Constraint Satisfaction Problems, i.e., satisfiability with more than two truth values.