A Generalization of SAT and #SAT for Robust Policy Evaluation (CMU-CS-13-107)

Erik Zawadski, André Platzer, Geoffrey J. GordonResearch 2018 · DOI

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{zawadski2018generalization,
  author = {Erik Zawadski and André Platzer and Geoffrey J. Gordon},
  title = {{A Generalization of SAT and \#SAT for Robust Policy Evaluation (CMU-CS-13-107)}},
  booktitle = {Research},
  year = {2018},
  doi = {10.1184/r1/6587453},
}

Loading related content...

Figure