Show simple item record

How Many Solutions Does a SAT Instance Have?

dc.contributor.authorPari, Pushkin R.
dc.contributor.authorYuan, Lin
dc.contributor.authorQu, Gang
dc.identifier.citationP. Pari, L. Yuan, and G. Qu. "How Many Solutions Does a SAT Instance Have?" IEEE International Symposium on Circuits and Systems, Vol. 5, pp. 209-212, May 2004.en
dc.description.abstractOur 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.en
dc.format.extent311595 bytes
dc.subjectBoolean Satisfiability (SAT) instanceen
dc.subjectSolves the instance Once and Finds All Solutions (SOFAS)en
dc.titleHow Many Solutions Does a SAT Instance Have?en
dc.relation.isAvailableAtA. James Clark School of Engineeringen_us
dc.relation.isAvailableAtElectrical & Computer Engineeringen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us
dc.rights.licenseCopyright © 2004 IEEE. Reprinted from IEEE International Symposium on Circuits and Systems. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the University of Maryland's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

Files in this item


This item appears in the following Collection(s)

Show simple item record