---
title: "Quantified Constraint Satisfaction Problems: From Relaxations to Explanations"
authors:
  - "Alex Ferguson"
  - "Barry O'Sullivan"
doi: ""
url: "https://ijcai.org/proceedings/2007/10"
pdf: "https://ijcai.org/proceedings/2007/0010.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "74-78"
track: ""
keywords:
---

# Quantified Constraint Satisfaction Problems: From Relaxations to Explanations

Alex Ferguson, Barry O'Sullivan

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 74-78.

## Abstract

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.