Bounded-width QBF is PSPACE-complete

DOI10.4230/LIPICS.STACS.2013.44MaRDI QIDQ2957870zbMATH OpenOpenAlexFDO

Authors Albert Atserias, Sergi Oliva

Publication date 30 January 2017

Full work available at URL http://upcommons.upc.edu/bitstream/2117/20304/1/Atserias.pdf

zbMATH Keywords

PSPACE-completenessQBFtree-width

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Bounded-width QBF is PSPACE-complete
• Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings
• QBF as an alternative to Courcelle's theorem
• Treewidth with a quantifier alternation revisited
• Using decomposition-parameters for QBF: mind the prefix!

Cited in

(5)

• Bounded-width QBF is PSPACE-complete
• Quantifier reordering for QBF
• On the equivalence among problems of bounded width
• Treewidth with a quantifier alternation revisited
• Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings

This page was built for publication: Bounded-width QBF is PSPACE-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957870)