The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 150-154.
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.
@inproceedings{ijcai2005p148,
title = {The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions},
author = {Gottlob, Georg and Greco, Gianluigi and Scarcello, Francesco},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {150--154},
year = {2005},
url = {https://ijcai.org/proceedings/2005/148},
}
TY - CPAPER TI - The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions AU - Gottlob, Georg AU - Greco, Gianluigi AU - Scarcello, Francesco T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 150 EP - 154 UR - https://ijcai.org/proceedings/2005/148 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
