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
Social Program
Location and Venue
Colocated Events
Authors' instructions
Print current pagePrint 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 Valid HTML 4.01! Valid CSS! Debian