Lucas Bordeaux, Marco Cadoli, Toni Mancini
Quantified constraints and Quantified Boolean Formulae are typically much more difficult to reason with than classical constraints, because quantifier alternation makes the simple, classical notion of solution inappropriate. As a consequence, even such essential CSP properties as consistency or substitutability are not completely understood in the quantified case. In this paper, we show that most of the properties which are used by solvers for CSP can be generalized to Quantified CSP. We propose a systematic study of the relations which hold between these properties, as well as complexity results regarding the decision of these properties. Finally, and since these problems are typically intractable, we generalise the approach used in CSP and propose weakenings of these notions based on locality, which allow for a tractable, albeit incomplete detecting of these properties.
Content Area: 6. Constraint Satisfaction and Satisfiability
Subjects: 15.2 Constraint Satisfaction; 9.2 Computational Complexity
Submitted: May 10, 2005