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,
Question   What is the computational complexity of QBF(Bounded Treewidth)? Is it PSPACE-complete? In PTIME?


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


Comments are limited to a maximum of 1000 characters.
More information about formatting options