Bodirsky, Manuel ;
Wrona, Michal
Equivalence Constraint Satisfaction Problems
Abstract
The following result for finite structures Gamma has been conjectured to hold for all countably infinite omegacategorical structures Gamma: either the modelcomplete core Delta of Gamma has an expansion by finitely many constants such that the pseudovariety generated by its polymorphism algebra contains a twoelement algebra all of whose operations are projections, or there is a homomorphism f from Delta^k to Delta, for some finite k, and an automorphism alpha of Delta satisfying f(x1,...,xk) = alpha(f(x2,...,xk,x1)). This conjecture has been confirmed for all infinite structures Gamma that have a firstorder definition over (Q;<), and for all structures that are definable over the random graph. In this paper, we verify the conjecture for all structures that are definable over an equivalence relation with a countably infinite number of countably infinite classes.
Our result implies a complexity dichotomy (into NPcomplete and P) for a family of constraint satisfaction problems (CSPs) which we call equivalence constraint satisfaction problems. The classification for equivalence CSPs can also be seen as a first step towards a classification of the CSPs for all relational structures that are firstorder definable over Allen's interval algebra, a wellknown constraint calculus in temporal reasoning.
BibTeX  Entry
@InProceedings{bodirsky_et_al:LIPIcs:2012:3668,
author = {Manuel Bodirsky and Michal Wrona},
title = {{Equivalence Constraint Satisfaction Problems}},
booktitle = {Computer Science Logic (CSL'12)  26th International Workshop/21st Annual Conference of the EACSL},
pages = {122136},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897422},
ISSN = {18688969},
year = {2012},
volume = {16},
editor = {Patrick C{\'e}gielski and Arnaud Durand},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3668},
URN = {urn:nbn:de:0030drops36689},
doi = {10.4230/LIPIcs.CSL.2012.122},
annote = {Keywords: Constraint satisfaction problems, universal algebra, model theory, Ram sey theory, temporal reasoning, computational complexity}
}
03.09.2012
Keywords: 

Constraint satisfaction problems, universal algebra, model theory, Ram sey theory, temporal reasoning, computational complexity 
Seminar: 

Computer Science Logic (CSL'12)  26th International Workshop/21st Annual Conference of the EACSL

Issue date: 

2012 
Date of publication: 

03.09.2012 