Bounded-width QBF is PSPACE-complete

作者：

Highlights：

• We solve an open problem on the complexity of bounded tree-width QBF.

• We show that the bounded tree-width QBF problem is PSPACE-complete.

• We present a family of formulas with bounded tree-width with short refutations.

摘要

•We solve an open problem on the complexity of bounded tree-width QBF.•We show that the bounded tree-width QBF problem is PSPACE-complete.•We present a family of formulas with bounded tree-width with short refutations.

论文关键词：Tree-width,Path-width,Quantified Boolean formulas,PSPACE-complete

论文评审过程：Received 15 March 2013, Revised 11 March 2014, Accepted 8 April 2014, Available online 15 April 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.04.014