Please use this identifier to cite or link to this item: https://doi.org/10.1109/SYNASC.2007.16
DC FieldValue
dc.titleApproximate satisfiability counting
dc.contributor.authorAndrei, Ş.
dc.contributor.authorYap, R.H.C.
dc.contributor.authorManolache, G.
dc.contributor.authorFelea, V.
dc.date.accessioned2013-07-04T08:31:47Z
dc.date.available2013-07-04T08:31:47Z
dc.date.issued2007
dc.identifier.citationAndrei, Ş., 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
dc.identifier.isbn0769530788
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/41620
dc.description.abstractThe 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1109/SYNASC.2007.16
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1109/SYNASC.2007.16
dc.description.sourcetitleProceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007
dc.description.page196-202
dc.identifier.isiut000264583000028
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

1
checked on Feb 18, 2020

WEB OF SCIENCETM
Citations

1
checked on Feb 18, 2020

Page view(s)

81
checked on Feb 19, 2020

Google ScholarTM

Check

Altmetric


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