Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • A. James Clark School of Engineering
    • Electrical & Computer Engineering
    • Electrical & Computer Engineering Research Works
    • View Item
    •   DRUM
    • A. James Clark School of Engineering
    • Electrical & Computer Engineering
    • Electrical & Computer Engineering Research Works
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    How Many Solutions Does a SAT Instance Have?

    Thumbnail
    View/Open
    c038.pdf (304.2Kb)
    No. of downloads: 542

    Date
    2004-05
    Author
    Pari, Pushkin R.
    Yuan, Lin
    Qu, Gang
    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.
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1903/9065
    Collections
    • Electrical & Computer Engineering Research Works
    Rights
    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.

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility