ω-CATEGORICAL STRUCTURES AVOIDING HEIGHT 1 IDENTITIES

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437375" target="_blank" >RIV/00216208:11320/21:10437375 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1090/tran/8179" target="_blank" >10.1090/tran/8179</a>

Jazyk výsledku

angličtina

Název v původním jazyce

ω-CATEGORICAL STRUCTURES AVOIDING HEIGHT 1 IDENTITIES

Popis výsledku v původním jazyce

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.

Název v anglickém jazyce

ω-CATEGORICAL STRUCTURES AVOIDING HEIGHT 1 IDENTITIES

Popis výsledku anglicky

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

R - Projekt Ramcoveho programu EK

Rok uplatnění

2021

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

Transactions of the American Mathematical Society [online]

ISSN

1088-6850

e-ISSN

—

Svazek periodika

2021

Číslo periodika v rámci svazku

374

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

24

Strana od-do

327-350

Kód UT WoS článku

000604947700010

EID výsledku v databázi Scopus

2-s2.0-85097878129