2007 · 92 citations · 14 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationBoolean OperationsConstraint SatisfactionBoolean SatisfiabilityBoolean Satisfiability ProblemLocal SearchLocal Search AlgorithmsLower BoundsSatisfiabilitySatisfiability ProblemSolution Space Exploration
The paper introduces a new technique for counting models of Boolean satisfiability problems. The method uses sampling of the solution space, converting local search samples into guaranteed bounds on the model count without requiring uniformity. Formal analysis and experiments demonstrate the effectiveness of the proposed counting technique.
We introduce a new technique for counting models of Boolean satisfiability problems. Our approach incorporates information obtained from sampling the solution space. Unlike previous approaches, our method does not require uniform or near-uniform samples. It instead converts local search sampling without any guarantees into very good bounds on the model count with guarantees. We give a formal analysis and provide experimental results showing the effectiveness of our approach.
14
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Evidence for invariants in local search
David McAllester, Bart Selman, Henry Kautz · 1997 · 368 citations
On the computational power of PP and (+)P
Seinosuke Toda · 1989 · 236 citations