文章基本信息

标题：Bounded-width QBF is PSPACE-complete
本地全文：下载
作者：Albert Atserias ; Sergi Oliva
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：20
页码：44-54
DOI：10.4230/LIPIcs.STACS.2013.44
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Tree-width; QBF; PSPACE-complete