文章基本信息

标题：DPLL with Caching: A new algorithm for #SAT and Bayesian Inference
本地全文：下载
作者：Fahiem Bacchus ; Shannon Dalmao ; Toniann Pitassi 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：Bayesian inference , Resolution , satisfiability , sharpSAT