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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.