Distance constraint satisfaction problems

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331263" target="_blank" >RIV/00216208:11320/16:10331263 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.ic.2015.11.010" target="_blank" >http://dx.doi.org/10.1016/j.ic.2015.11.010</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2015.11.010" target="_blank" >10.1016/j.ic.2015.11.010</a>

Result language
angličtina
Original language name
Distance constraint satisfaction problems
Original language description
We study the complexity of constraint satisfaction problems for templates Gamma over the integers where the relations are first-order definable from the successor function. In the case that Gamma is locally finite (i.e., the Gaifman graph of Gamma has finite degree), we show that Gamma is homomorphically equivalent to a structure with one of two classes of polymorphisms (which we call modular max and modular min) and the CSP for Gamma can be solved in polynomial time, or Gamma is homomorphically equivalent to a finite transitive structure, or the CSP for Gamma is NP-complete. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), this proves that those CSPs have a complexity dichotomy, that is, are either in P or NP-complete.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)