Tue, 8 Apr 2025, 1:25 pm MDT
The Constraint Satisfaction Problem (CSP) over a structure $\mathfrak{B}$ with a finite relational signature is the problem of deciding whether a given finite input structure $\mathfrak{A}$ with the same signature as $\mathfrak{B}$ has a homomorphism to $\mathfrak{B}$. According to the famous result of Bulatov and Zhuk we know that CSPs over finite template structures exhibit a complexity dichotomy: they are all in $\mathbf{P}$ or $\mathbf{NP}$-complete. Generalizing this theorem to infinite structures has been a topic of active research in the past few decades. A currently standing conjecture in this direction is by Bodirsky and Pinsker which states that the same complexity dichotomy holds for first-order reducts of finitely bounded homogeneous structures. In my talk I am exploring some ideas on how this conjecture could be attacked under some strong model theoretical assumptions such as $\omega$-stability or first-order interpretability in the pure set. This approach often requires a detailed understanding of structures arising in this context which also leads to some questions in model theory that could be of independent interest.
This is a joint work with Manuel Bodirsky and Paolo Marimon.