Complexity of QBF(Bounded Treewidth) (Solved)

Importance: Medium ✭✭
Author(s): Moshe Y. Vardi
Recomm. for undergrads: no
Posted by: myvardi
on: May 18th, 2012
Solved by: Albert Atserias and Sergi Oliva, http://www.lsi.upc.edu/~atserias/papers/qbfboundedwidth/qbfboundedwidth.pdf
Question   What is the computational complexity of QBF(Bounded Treewidth)? Is it PSPACE-complete? In PTIME?

Bibliography

[1] G. Pan, M. Y. Vardi, Fixed-Parameter Hierarchies inside PSPACE, LICS 2006, pp.27-36, 21st Annual IEEE Symposium on Logic in Computer Science, 2006.


* indicates original appearance(s) of problem.