Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation
Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer · 2005
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 that hardness results carry over to the case of arbitrary finite domains.