Programming Research Group Research Report RR-02-11

Ferdinand Borner, Andrei Krokhin, Andrei Bulatov, and Peter Jeavons

November 2002, 25pp.

Abstract

The constraint satisfaction problem over an arbitrary finite domain can be parameterized by the set of allowed constraint predicates, and the complexity of the parameterized problem is known to be determined by the polymorphisms of those 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.