---
title: "The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions"
authors:
  - "Georg Gottlob"
  - "Gianluigi Greco"
  - "Francesco Scarcello"
doi: ""
url: "https://ijcai.org/proceedings/2005/148"
pdf: "https://ijcai.org/proceedings/2005/0148.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "150-154"
track: ""
keywords:
---

# The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions

Georg Gottlob, Gianluigi Greco, Francesco Scarcello

*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.