Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR12-096 | 9th January 2013 13:15

Bounded-width QBF is PSPACE-complete

RSS-Feed




Revision #3
Authors: Albert Atserias, Sergi Oliva
Accepted on: 9th January 2013 13:15
Downloads: 2370
Keywords: 


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 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.



Changes to previous version:

Fixed some typos.


Revision #2 to TR12-096 | 19th September 2012 15:41

Bounded-width QBF is PSPACE-complete





Revision #2
Authors: Albert Atserias, Sergi Oliva
Accepted on: 19th September 2012 15:41
Downloads: 2544
Keywords: 


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.


Revision #1 to TR12-096 | 26th July 2012 19:08

Bounded-width QBF is PSPACE-complete





Revision #1
Authors: Albert Atserias, Sergi Oliva
Accepted on: 26th July 2012 19:08
Downloads: 1372
Keywords: 


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 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.



Changes to previous version:

Minor rewriting of introduction.


Paper:

TR12-096 | 17th July 2012 23:18

Bounded-width QBF is PSPACE-complete





TR12-096
Authors: Albert Atserias, Sergi Oliva
Publication: 26th July 2012 19:02
Downloads: 3333
Keywords: 


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 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.



ISSN 1433-8092 | Imprint