Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-036 | 28th March 2005 00:00

Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms



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 quantified constraint satisfaction problem (QCSP), a more general framework in which variables can be quantified both universally and existentially. We study the complexity of restricted cases of the QCSP where the types of constraints that may appear are restricted by a constraint language. We give a complete complexity classification of maximal constraint languages, the largest possible languages that can be tractable. We also give a complete complexity classification of constraint languages arising from symmetric polymorphisms.

ISSN 1433-8092 | Imprint