Please use this identifier to cite or link to this item: https://doi.org/10.1109/SYNASC.2007.16
Title: Approximate satisfiability counting
Authors: Andrei, Ş.
Yap, R.H.C. 
Manolache, G.
Felea, V.
Issue Date: 2007
Source: Andrei, Ş., Yap, R.H.C., Manolache, G., Felea, V. (2007). Approximate satisfiability counting. Proceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007 : 196-202. ScholarBank@NUS Repository. https://doi.org/10.1109/SYNASC.2007.16
Abstract: The problem of counting satisfiability, i.e. count the number of satisfying assignments for a SAT problem, is used successfully in a number of problems. For example, it can provide heuristics for guiding planning and search, where an estimation of the probability for a given search would help lead to a goal. Counting satisfiability is a valuable approach for problems like constraint satisfaction, knowledge compilation, probabilistic reasoning and computing the permanent of a Boolean matrix. The difficulty with counting satisfiability is that it is as hard as NP-complete problems, but probably much harder. This means that solvers to count the exact number of solutions may need a large amount on time on large propositional formulas. In this paper, we provide a fast alternative by approximating the number of instances. Our technique is based on successive variable and clause elimination. Experimental results demonstrate that our technique is promising. © 2008 IEEE.
Source Title: Proceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007
URI: http://scholarbank.nus.edu.sg/handle/10635/41620
ISBN: 0769530788
DOI: 10.1109/SYNASC.2007.16
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

1
checked on Nov 19, 2017

Page view(s)

56
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.