ω-CATEGORICAL STRUCTURES AVOIDING HEIGHT 1 IDENTITIES
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
ω-CATEGORICAL STRUCTURES AVOIDING HEIGHT 1 IDENTITIES
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
R - Projekt Ramcoveho programu EK
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Transactions of the American Mathematical Society [online]
ISSN
1088-6850
e-ISSN
—
Volume of the periodical
2021
Issue of the periodical within the volume
374
Country of publishing house
DE - GERMANY
Number of pages
24
Pages from-to
327-350
UT code for WoS article
000604947700010
EID of the result in the Scopus database
2-s2.0-85097878129