Abstract
Many natural decision problems can be formulated as constraint satisfaction problems for reducts of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. For such an infinite structure A, we present a general polynomial-time reduction from CSP(A) to CSP(T(A)), where T(A) is a finite structure. This allows us to obtain powerful new polynomial-time tractability conditions that can be expressed in terms of topological polymorphism clones. A function on a set D is said to be canonical with respect to the action of a group on D if it commutes in some loose sense with the group action: more precisely, a function is canonical if it induces a function on the set of orbits of k-tuples, for every integer k. If the complexity of the CSP of A is captured by the canonical polymorphisms of A, we also have a reduction in the opposite direction from T(A) to A. Using this approach we show that the algebraic dichotomy conjecture for finite-domain CSPs is equivalent to a similar dichotomy conjecture for the class of all structures that are definable using equality and constants.