How many solutions does a SAT instance have?
Authors:
- 30 November 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 5
Abstract
Our goal is to investigate the solution space of a given Boolean satisfiability (SAT) instance. In particular, we are interested in determining the size of the solution space - the number of truth assignments that make the SAT instance true - and finding all such truth assignments, if possible. This apparently hard problem has both theoretical and practical values. We propose an exact algorithm based on exhaustive search that solves the instance once and finds all solutions (SOFAS) and several sampling techniques that estimate the size of the solution space. SOFAS works better for SAT instances of small size with a 5X-100X speed-up over the brute force search algorithm. The sampling techniques estimate the solution space reasonably well for standard SAT benchmarks.Keywords
This publication has 4 references indexed in Scilit:
- GRASP-A new search algorithm for satisfiability2002
- Satometer:Proceedings of the 39th conference on Design automation - DAC '02, 2002
- Boolean satisfiability in electronic design automation2000
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960