Computer Science Logic and 8th Kurt Gödel Colloquium Manuel Bodirsky and Jaroslav Nesetril: Constraint Satisfaction with Countable Homogeneous Templates

Welcome and News Host Institutions Calls and Deadlines Program Social Program Registration Location and Venue Accommodation Committees Contact Colocated Events Authors' instructions

Print this page 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 first-order 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). © 2002-2003 Kurt Gödel Society, Norbert Preining. 2003-06-04