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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:77437 |
| Date | 18 January 2022 |
| Creators | Bodor, Bertalan |
| Contributors | Bodirsky, Manuel, Pinsker, Michael, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | info:eu-repo/grantAgreement/European Research Council/European Union’s Horizon 2020 research and innovation programme/681988//CSP-Infinity |
Page generated in 0.0019 seconds