Many natural computational problems can be formulated elegantly as CSPs over a countably infinite structure S (for example, given a digraph, decide whether or not it is acyclic). However, the price to pay for such a formulation is generally high, as there are many operations possibly proving tractability, and many relations possibly proving hardness of such CSPs, and both operations and relations are infinite objects. We present a general method for obtaining complexity classifications for the CSP of all structures which are first-order definable in an ordered homogeneous Ramsey structure. This method roughly consists in finding patterns of regular behaviour in arbitrary operations on the structure - such patterns allow to relate infinite operations (in particular, polymorphisms) to operations on finite sets, and to translate existing tractability results on finite sets back to the infinite. In particular, given a relation R in this context, it is possible to calculate a finite number of ”minimal” generic polymorphisms that violate R; such generic polymorphisms can be represented as finite functions, and used by algorithms. This implies, for example, that the following problem becomes decidable: Given a relation R and a relational structure S, both of which have first-order definitions in an ordered homogeneous Ramsey structure which is finitely bounded, does R have a primitive positive definition from S?

https://arxiv.org/abs/1105.6073