Michael Bauland, Elmar BĂ¶hler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>

Tomas Feder, Phokion G. Kolaitis

Quantified constraint satisfaction is the generalization of

constraint satisfaction that allows for both universal and existential

quantifiers over constrained variables, instead

of just existential quantifiers.

We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes

a pattern of quantifier alternation ending in exists or the set of all possible

more >>>