Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.44
URN: urn:nbn:de:0030-drops-39217
URL: https://drops.dagstuhl.de/opus/volltexte/2013/3921/
Atserias, Albert ; Oliva, Sergi
Bounded-width QBF is PSPACE-complete
| pdf-format: |
|
Abstract
Tree-width is a well-studied parameter of structures that measures their similarity to a tree. Many important NP-complete problems, such as Boolean satisfiability (SAT), are tractable on bounded tree-width instances. In this paper we focus on the canonical PSPACE-complete problem QBF, the fully-quantified version of SAT. It was shown by Pan and Vardi [LICS 2006] that this problem is PSPACE-complete even for formulas whose tree-width grows extremely slowly. Vardi also posed the question of whether the problem is tractable when restricted to instances of bounded tree-width. We answer this question by showing that QBF on instances with constant tree-width is PSPACE-complete.
BibTeX - Entry
@InProceedings{atserias_et_al:LIPIcs:2013:3921,
author = {Albert Atserias and Sergi Oliva},
title = {{Bounded-width QBF is PSPACE-complete}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {44--54},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-50-7},
ISSN = {1868-8969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3921},
URN = {urn:nbn:de:0030-drops-39217},
doi = {10.4230/LIPIcs.STACS.2013.44},
annote = {Keywords: Tree-width, QBF, PSPACE-complete}
}
| Keywords: | Tree-width, QBF, PSPACE-complete | |
| Seminar: | 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) | |
| Issue date: | 2013 | |
| Date of publication: | 26.02.2013 |
