2026-07-20T05:41:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3668 2024-03-06T10:34:20Z ddc:004 open_access

Equivalence Constraint Satisfaction Problems Bodirsky, Manuel Wrona, Michal Constraint satisfaction problems universal algebra model theory Ram- sey theory temporal reasoning computational complexity The following result for finite structures Gamma has been conjectured to hold for all countably infinite omega-categorical structures Gamma: either the model-complete core Delta of Gamma has an expansion by finitely many constants such that the pseudovariety generated by its polymorphism algebra contains a two-element 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 first-order 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 NP-complete 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 first-order definable over Allen's interval algebra, a well-known constraint calculus in temporal reasoning. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Michal Wrona 2012 Is Part Of LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2012.122 urn:nbn:de:0030-drops-36689 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.122 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode