ALCOMFT-TR-03-54

F. Boerner, A. Bulatov, P. Jeavons and A. Krokhin
Quantified constraints: Algorithms and complexity
Warwick. Work package 4. October 2003.

Abstract: 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 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.

Keywords: non-Boolean quantified constraint satisfaction problem, constraint predicates, complexity, algorithms, polymorphisms.

Postscript file: ALCOMFT-TR-03-54.ps.gz (130 kb).