An Algebraic Approach to Multi-sorted Constraints

Abstract. Most previous theoretical study of the complexity of the constraint satisfaction problem has considered a simplified version of the problem in which all variables have the same domain. We show here that this apparently minor simplification can in fact change the complexity of the problem, and hence mask the existence of certain tractable constraint types. In this paper we describe a new algebraic framework which allows us to deal more precisely with problems where different variables may have different domains. Using this new framework we are able to identify new tractable classes of constraints, by combining algorithms devised for the simplified, single domain, problem. We also systematically develop an algebraic structural theory for the general problem, and show that this theory can be used to generalise earlier results about the complexity of certain constraint types.