Distance constraint satisfaction problems

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Distance constraint satisfaction problems

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Distance constraint satisfaction problems

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název periodika

Information and Computation

ISSN

0890-5401

e-ISSN

—

Svazek periodika

2016

Číslo periodika v rámci svazku

247

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

87-105

Kód UT WoS článku

000372136400005

EID výsledku v databázi Scopus

2-s2.0-84954288234