An Algebraic Hardness Criterion for Surjective Constraint Satisfaction

The constraint satisfaction problem (CSP) is a computational problem in which one is to decide, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This problem appears in many guises throughout computer science, for instance, in database theory, artificial intelligence, and the study of graph homomorphisms. One obtains a rich and natural family of problems by defining, for each relational structure B, the problem CSP(B) to be the case of the CSP where the relations used to specify constraints must come fromB. An increasing literature studies the algorithmic and complexity behavior of this problem family, focusing on finite and finite-like structures [1, 12, 2]; a primary research issue is to determine which such problems are polynomial-time tractable, and which are not. To this end of classifying problems, a so-called algebraic approach has been quite fruitful [5]. In short, this approach is founded on the facts that the complexity of a problem CSP(B) depends (up to polynomial-time reducibility) only on the set of relations that are primitive positive definable from B, and that this set of relations can be derived from the clone of polymorphisms ofB. Hence, the project of classifying all relational structures according to the complexity of CSP(B) can be formulated as a classification question on clones; 1 this permits the employment of algebraic notions and techniques in this project.