
For a fixed countable homogeneous structure Gamma we study the computational problem whether a given finite structure of the same relational signature homomorphically maps to Gamma. This problem is known as the constraint satisfaction problem CSP(Gamma) for Gamma and was intensively studied for finite Gamma. We show that  as in the case of finite Gamma  the computational complexity of CSP(Gamma) for countable homogeneous Gamma is determinded by the clone of polymorphisms of Gamma. To this end we prove the following theorem which is of independent interest: A given firstorder definable relation over a countable homogeneous template Gamma has a primitive positive definition if and only if it is invariant under the polymorphisms of Gamma.
Constraint satisfaction with countable homogeneous templates is a proper generalization of constraint satisfaction with finite templates. If the age of Gamma is finitely axiomatizable, then CSP(Gamma) is in NP. If Gamma is a digraph we can use the classification of homogeneous digraphs by Cherlin to determine the complexity of CSP(Gamma).
© 20022003 Kurt Gödel Society, Norbert Preining. 
20030604
 