|
Organizers |
Countable homogeneous structures, local clones, and constraint satisfaction
by
Manuel Bodirsky
Humboldt Universitaet zu Berlin
Many interesting constraint satisfaction problems in theoretical computer science are equivalent to the question: Is there a homomorphism of a given finite relational structure to a countable homogeneous structure of the same signature? We show that the computational complexity of such problems can be characterized by the clone of polymorphisms of the countable homogeneous structure.
Date received: January 29, 2003
Copyright © 2003 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cake-28.