Solving and Sampling with Many Solutions

• Published in: Algorithmica 2020-05, Vol.82 (5), p.1474-1489
• Main Authors: Cardinal, Jean, Nummenpalo, Jerri, Welzl, Emo
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Mathematics of Computing; Sampling; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-019-00654-w

We investigate the complexity of satisfiability problems parameterized by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time O ∗ ( ε - 0.617 ) where ε is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected  Θ ∗ ( ε - 1 ) , and on all previous algorithms whenever ε = Ω ( 0 . 708 n ) , where n is the number of variables. We also consider algorithms for 3-SAT with an ε fraction of satisfying assignments, and prove that we can output a satisfying assignment in O ∗ ( ε - 0.936 ) randomized time, and sample uniformly a satisfying assignment in time O ∗ ( ε - 0.908 1 . 021 n ) . In the end we also present sampling results in the cases of 1-IN-3-SAT, monotone bounded degree 3-SAT and planar k -SAT.