Open Problem Garden

Importance: Medium ✭✭

Author(s):

Subject:	Logic
	» Finite Model Theory

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.