TOPOLOGY IS IRRELEVANT (IN A DICHOTOMY CONJECTURE FOR INFINITE DOMAIN CONSTRAINT SATISFACTION PROBLEMS)

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10421064" target="_blank" >RIV/00216208:11320/20:10421064 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=qhDISn9fvW" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=qhDISn9fvW</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/18M1216213" target="_blank" >10.1137/18M1216213</a>

Jazyk výsledku

angličtina

Název v původním jazyce

TOPOLOGY IS IRRELEVANT (IN A DICHOTOMY CONJECTURE FOR INFINITE DOMAIN CONSTRAINT SATISFACTION PROBLEMS)

Popis výsledku v původním jazyce

( )The tractability conjecture for finite domain constraint satisfaction problems (CSPs) stated that such CSPs are solvable in polynomial time whenever there is no natural reduction, in some precise technical sense, from the 3-SAT problem; otherwise, they are NP-complete. Its recent resolution draws on an algebraic characterization of the conjectured borderline: the CSP of a finite structure permits no natural reduction from 3-SAT if and only if the stabilizer of the polymorphism clone of the core of the structure satisfies some nontrivial system of identities, and such satisfaction is always witnessed by several specific nontrivial systems of identities which do not depend on the structure. The tractability conjecture has been generalized in the above formulation to a certain class of infinite domain CSPs, namely, CSPs of reducts of finitely bounded homogeneous structures. It was subsequently shown that the conjectured borderline between hardness and tractability, i.e., a natural reduction from 3-SAT, can be characterized for this class by a combination of algebraic and topological properties. However, it was not known whether the topological component is essential in this characterization. We provide a negative answer to this question by proving that the borderline is characterized by one specific algebraic identity, namely, the pseudo-Siggers identity alpha s(x, y, x, z, y, z) approximate to beta s(y, x, z, x, z, y). This accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our main theorem is also of independent mathematical interest, characterizing a topological property of any omega-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).

Název v anglickém jazyce

TOPOLOGY IS IRRELEVANT (IN A DICHOTOMY CONJECTURE FOR INFINITE DOMAIN CONSTRAINT SATISFACTION PROBLEMS)

Popis výsledku anglicky

( )The tractability conjecture for finite domain constraint satisfaction problems (CSPs) stated that such CSPs are solvable in polynomial time whenever there is no natural reduction, in some precise technical sense, from the 3-SAT problem; otherwise, they are NP-complete. Its recent resolution draws on an algebraic characterization of the conjectured borderline: the CSP of a finite structure permits no natural reduction from 3-SAT if and only if the stabilizer of the polymorphism clone of the core of the structure satisfies some nontrivial system of identities, and such satisfaction is always witnessed by several specific nontrivial systems of identities which do not depend on the structure. The tractability conjecture has been generalized in the above formulation to a certain class of infinite domain CSPs, namely, CSPs of reducts of finitely bounded homogeneous structures. It was subsequently shown that the conjectured borderline between hardness and tractability, i.e., a natural reduction from 3-SAT, can be characterized for this class by a combination of algebraic and topological properties. However, it was not known whether the topological component is essential in this characterization. We provide a negative answer to this question by proving that the borderline is characterized by one specific algebraic identity, namely, the pseudo-Siggers identity alpha s(x, y, x, z, y, z) approximate to beta s(y, x, z, x, z, y). This accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our main theorem is also of independent mathematical interest, characterizing a topological property of any omega-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA13-01832S" target="_blank" >GA13-01832S: Obecná algebra a její souvislost s informatikou</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

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

SIAM Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

2020

Číslo periodika v rámci svazku

49

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

29

Strana od-do

365-393

Kód UT WoS článku

000546873800004

EID výsledku v databázi Scopus

2-s2.0-85084414747