Please use this identifier to cite or link to this item:
|Title:||Approximate satisfiability counting||Authors:||Andrei, Ş.
|Issue Date:||2007||Citation:||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.
checked on Sep 20, 2019
WEB OF SCIENCETM
checked on Sep 12, 2019
checked on Sep 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.