Quantified constraint satisfaction problems: From relaxations to explanations

The Quantified Constraint Satisfaction Problem (QCSP) is a generalisation of the classical CSP in which some of variables can be universally quantified. In this paper, we extend two well-known concepts in classical constraint satisfaction to the quantified case: problem relaxation and explanation of inconsistency. We show that the generality of the QCSP allows for a number of different forms of relaxation not available in classical CSP . We further present an algorithmfor computing a generalisation of conflict-based explanations of inconsistency for the QCSP.