CSP dichotomy for ω-categorical monadically stable structures

Bertalan Bodor

AutorIn

Bertalan Bodor

Titel

CSP dichotomy for ω-categorical monadically stable structures

Zitierfähige Url:

https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-774379

Erstveröffentlichung

2022

Datum der Einreichung

21.05.2021

Datum der Verteidigung

06.12.2021

Abstract (EN)

The constraint satisfaction problem (CSP) over a structure A with a finite relational signature, denoted by CSP(A), is the problem of deciding whether a given finite structure B with the same signature as A has a homomorphism to A. Using concepts and techniques from universal algebra, Bulatov and Zhuk proved independently that if A is finite, then the CSP over A is always in P or NP-complete. Following this result, it is a natural question to ask when and how this dichotomy can be generalized for infinite structures. The infinite-domain CSP dichotomy conjecture (originally formulated by Bodirsky and Pinsker [BPP14]) states that the same complexity dichotomy holds for first-order reducts of finitely bounded homogeneous structures. This conjecture has been solved for many special classes of structures. In this thesis we are developing new techniques involving canonical polymorphisms to attack this conjecture. Using these techniques we prove a new CSP dichotomy result, namely we show that the CSP over every finitely related ω-categorical monadically stable structure is in P or NP-complete.

Freie Schlagwörter (DE)

CSP, ω-kategorisch, monadische Stabilität, kanonische Funktionen

Freie Schlagwörter (EN)

CSP, ω-categorical, monadic stability, canonical functions

Klassifikation (DDC)

510

Klassifikation (RVK)

SK 680

GutachterIn