Hrushovski's Encoding and ω-Categorical CSP Monsters

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

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Hrushovski's Encoding and ω-Categorical CSP Monsters

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Hrushovski's Encoding and ω-Categorical CSP Monsters

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

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 statě ve sborníku

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

—

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

17

Strana od-do

1-17

Název nakladatele

Schloss Dagstuhl-Leibniz

Místo vydání

Německo

Místo konání akce

SRN, online

Datum konání akce

8. 7. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—