Relatively quantified constraint satisfaction |
| |
Authors: | Manuel Bodirsky Hubie Chen |
| |
Affiliation: | (1) Laboratoire d’informatique (LIX), école Polytechnique, Paris, France;(2) Departament de Tecnologies de la Informació i les Comunicacions, Universitat Pompeu Fabra, Barcelona, Spain |
| |
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 |
本文献已被 SpringerLink 等数据库收录! |
|