The Complexity of Quantified Constraint Satisfaction Problems Under Structural Restrictions
Abstract
We give a clear picture of the tractability/intractability frontier for quantified constraint satisfaction problems (QCSPs) under structural restrictions.On the negative side, we prove that checking QCSP satisfiability remains PSPACE-hard for all known structural properties more general than bounded treewidth and for the incomparable hypergraph acyclicity.Moreover, if the domain is not fixed, the problem is PSPACE-hard even for tree-shaped constraint scopes.On the positive side, we identify relevant tractable classes, including QCSPs with prefix having bounded hypertree width, and QCSPs with a bounded number of guards.The latter are solvable in polynomial time without any bound on domains or quantifier alternations.
Cite
Text
Gottlob et al. "The Complexity of Quantified Constraint Satisfaction Problems Under Structural Restrictions." International Joint Conference on Artificial Intelligence, 2005.Markdown
[Gottlob et al. "The Complexity of Quantified Constraint Satisfaction Problems Under Structural Restrictions." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/gottlob2005ijcai-complexity/)BibTeX
@inproceedings{gottlob2005ijcai-complexity,
title = {{The Complexity of Quantified Constraint Satisfaction Problems Under Structural Restrictions}},
author = {Gottlob, Georg and Greco, Gianluigi and Scarcello, Francesco},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2005},
pages = {150-155},
url = {https://mlanthology.org/ijcai/2005/gottlob2005ijcai-complexity/}
}