Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-003 | 19th December 2002 00:00

DPLL with Caching: A new algorithm for #SAT and Bayesian Inference

RSS-Feed




TR03-003
Authors: Fahiem Bacchus, Shannon Dalmao
Publication: 16th January 2003 00:34
Downloads: 1692
Keywords: 


Abstract:

Bayesian inference and counting satisfying assignments are important
problems with numerous applications in probabilistic reasoning. In this
paper, we show that plain old DPLL equipped with memoization can solve
both of these problems with time complexity that is at least as
good as all known algorithms. Furthermore, DPLL with memoization
achieves the best known time-space tradeoff. Our DPLL based algorithms
have the potential to acheive better average-case performance than
known algorithms on problems which possess additional structure.
Probabilistic models of real situations tend to have such additional
structure.



ISSN 1433-8092 | Imprint