Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-024 | 8th February 2005 00:00

Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint