Computer Science Logic and 8th Kurt Gödel Colloquium
Ferdinand Boerner, Andrei Bulatov, Peter Jeavons, Andrei Krokhin: Quantified Constraints: Algorithms and Complexity
Welcome and News
Host Institutions
Calls and Deadlines
Social Program
Location and Venue
Colocated Events
Authors' instructions
Print current pagePrint this page
The standard constraint satisfaction problem over an arbitrary finite domain can be expressed as follows: given a first-order sentence consisting of a conjunction of predicates, where all of the variables are existentially quantified, determine whether the sentence is true. This problem can be parameterized by the set of allowed constraint predicates. With each predicate, one can associate a set of certain predicate-preserving operations, called polymorphisms, and the complexity of the parameterized problem is known to be determined by the polymorphisms of the allowed predicates. In this paper we consider a more general framework for constraint satisfaction problems which allows arbitrary quantifiers over constrained variables, rather than just existential quantifiers. By considering a new Galois correspondence between sets of predicates and sets of operations, we show that the complexity of such extended problems is determined by the surjective polymorphisms of the constraint predicates. We give examples to illustrate how this result can be used to identify tractable and intractable cases for the quantified constraint satisfaction problem over arbitrary finite domains. Finally, we apply the techniques presented here to obtain a trichotomy theorem for the complexity of such problems when the parameter set contains all graphs of permutations: we show that they are either tractable, or NP-complete, or PSPACE-complete.
© 2002-2003 Kurt Gödel Society, Norbert Preining. 2003-06-04 Valid HTML 4.01! Valid CSS! Debian