Title: Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation
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.
Publication Year: 2005
Publication Date: 2005-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 6
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot