Hrushovski's Encoding and ω-Categorical CSP Monsters

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420930" target="_blank" >RIV/00216208:11320/20:10420930 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ICALP.2020.131" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2020.131</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2020.131" target="_blank" >10.4230/LIPIcs.ICALP.2020.131</a>

Result language
angličtina
Original language name
Hrushovski's Encoding and ω-Categorical CSP Monsters
Original language description
We produce a class of ω-categorical structures with finite signature by applying a model-theoretic construction - a refinement of an encoding due to Hrushosvki - to ω-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate ω-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and ω-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of ω-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA13-01832S" target="_blank" >GA13-01832S: General algebra and its connections to computer science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
—
ISSN
1868-8969
e-ISSN
—
Number of pages
17
Pages from-to
1-17
Publisher name
Schloss Dagstuhl-Leibniz
Place of publication
Německo
Event location
SRN, online
Event date
Jul 8, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)