Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Bounded-width QBF is PSPACE-complete

Autor
Atserias, A.; Oliva, S.
Tipus d'activitat
Article en revista
Revista
Journal of computer and system sciences
Data de publicació
2014-11-01
Volum
80
Número
7
Pàgina inicial
1415
Pàgina final
1429
DOI
https://doi.org/10.1016/j.jcss.2014.04.014 Obrir en finestra nova
Projecte finançador
Métodos formales y algoritmos para el diseño de sistemas
TIN2010-20967-C04-04
Repositori
http://hdl.handle.net/2117/27300 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0022000014000580 Obrir en finestra nova
Resum
Tree-width and path-width are two well-studied parameters of structures that measure their similarity to a tree and a path, respectively. We show that QBF on instances with constant path-width, and hence constant tree-width, remains PSPACE-complete. This answers a question by Vardi. We also show that on instances with constant path-width and a very slow-growing number of quantifier alternations (roughly inverse-Ackermann many in the number of variables), the problem remains NP-hard. Additionally...
Citació
Atserias, A.; Oliva, S. "Journal of computer and system sciences". 01 Novembre 2014.
Paraules clau
PSPACE-complete, Path-width, Quantified Boolean formulas, Tree-width
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius