Volume 14, Number 1, 3-15, DOI: 10.1007/s10601-008-9054-z

Relatively quantified constraint satisfaction

Manuel Bodirsky and Hubie Chen

From the issue entitled "Special Issue on Quantified CSPs and QBF; Guest Editors: Enrico Giunchiglia and Kostas Stergiou"

View Related Documents

Abstract

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the more general framework of quantified constraint satisfaction, in which variables can be quantified both universally and existentially. We study the relatively quantified constraint satisfaction problem (RQCSP), in which the values for each individual variable can be arbitrarily restricted. We give a complete complexity classification of the cases of the RQCSP where the types of constraints that may appear are specified by a constraint language.

Keywords  Quantified constraint satisfaction - Computational complexity

Fulltext Preview

Image of the first page of the fulltext document