2026-07-23T04:54:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3921 2024-03-06T10:34:38Z ddc:004 open_access

Bounded-width QBF is PSPACE-complete Atserias, Albert Oliva, Sergi Tree-width QBF PSPACE-complete 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Albert Atserias and Sergi Oliva 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.44 urn:nbn:de:0030-drops-39217 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.44 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode