Relatively Quantified Constraint Satisfaction

摘要

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.