How Many Solutions Does a SAT Instance Have?
| dc.contributor.author | Pari, Pushkin R. | |
| dc.contributor.author | Yuan, Lin | |
| dc.contributor.author | Qu, Gang | |
| dc.date.accessioned | 2009-05-11T13:53:36Z | |
| dc.date.available | 2009-05-11T13:53:36Z | |
| dc.date.issued | 2004-05 | |
| dc.description.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. | en |
| dc.format.extent | 311595 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.citation | P. 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.identifier.uri | http://hdl.handle.net/1903/9065 | |
| dc.language.iso | en_US | en |
| dc.publisher | IEEE | en |
| dc.relation.isAvailableAt | A. James Clark School of Engineering | en_us |
| dc.relation.isAvailableAt | Electrical & Computer Engineering | en_us |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_us |
| dc.relation.isAvailableAt | University of Maryland (College Park, MD) | en_us |
| dc.rights.license | Copyright © 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 pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it. | |
| dc.subject | Boolean Satisfiability (SAT) instance | en |
| dc.subject | Solves the instance Once and Finds All Solutions (SOFAS) | en |
| dc.title | How Many Solutions Does a SAT Instance Have? | en |
| dc.type | Article | en |
Files
Original bundle
1 - 1 of 1