Solving and sampling with many solutions: satisfiability and other hard problems

DOI10.4230/LIPICS.IPEC.2017.11MaRDI QIDQ5111870zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Jerri Nummenpalo, Emo Welzl

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1708.01122

zbMATH Keywords

samplingparameterized complexitysatisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Abstract: We investigate parameterizing hard combinatorial problems 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^{\ast }(varepsilo{n}^{-0.617})$ where $varepsilon$ is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected $Thet{a}^{\ast }(varepsilo{n}^{-1})$, and on all previous algorithms whenever $varepsilon=Omega(0.708^n)$. We also consider algorithms for 3-SAT with an $varepsilon$ fraction of satisfying assignments, and prove that it can be solved in $O^{\ast }(varepsilo{n}^{-2.27})$ deterministic time, and in $O^{\ast }(varepsilo{n}^{-0.936})$ randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.

Recommendations

• Solving and sampling with many solutions
• scientific article; zbMATH DE number 2090009
• Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
• An approximation algorithm for \(\#k\)-SAT
• Why almost all satisfiable k-CNF formulas are easy

Cites work

• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• A fast deterministic algorithm for formulas that have many satisfying assignments
• A probabilistic algorithm for k-SAT based on limited local search and restart
• A short implicant of a CNF formula with many satisfying assignments
• A short proof for a theorem of Harper about Hamming-spheres
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• Improved pseudorandom generators for depth 2 circuits
• Random generation of combinatorial structures from a uniform distribution
• Solving and sampling with many solutions: satisfiability and other hard problems
• Solving satisfiability in less than \(2^ n\) steps
• Theory and Applications of Satisfiability Testing

Cited in

(3)

• Solving and sampling with many solutions
• Solving and sampling with many solutions: satisfiability and other hard problems
• Practically uniform solution sampling in constraint programming

This page was built for publication: Solving and sampling with many solutions: satisfiability and other hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111870)