A Generalization of SAT and #SAT for Robust Policy Evaluation
Lists
Only you see this
Abstract
Both SAT and #SAT can represent difficult problems in seemingly dissimilar areas such as planning, verification, and probabilistic inference.Here, we examine an expressive new language, #∃SAT, that generalizes both of these languages.#∃SAT problems require counting the number of satisfiable formulas in a concisely-describable set of existentially-quantified, propositional formulas.We characterize the expressiveness and worst-case difficulty of #∃SAT by proving it is complete for the complexity class #P NP [1] , and relating this class to more familiar complexity classes.We also experiment with three new general-purpose #∃SAT solvers on a battery of problem distributions including a simple logistics domain.Our experiments show that, despite the formidable worst-case complexity of #P NP [1] , many of the instances can be solved efficiently by noticing and exploiting a particular type of frequent structure.
BibTeX
@inproceedings{zawadzki2013generalization,
author = {Erik Zawadzki and André Platzer and Geoffrey J. Gordon},
title = {{A Generalization of SAT and \#SAT for Robust Policy Evaluation}},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
url = {https://openreview.net/forum?id=H1WBZBfOWH},
}Loading related content...