Algebra Seminar talk
The Bodirsky-Pinsker conjecture for reducts of hypergraphs
Many computational problems can be described as constraint satisfaction problems (CSPs). For CSPs over finite template, a complexity dichotomy conjecture was proven by Bulatov and Zhuk in 2017 (every such CSP is either polynomial-time solvable or NP-complete). For certain class of infinite-domain CSPs, a similar dichotomy was conjectured to be true by Bodirsky and Pinsker. We discuss the recent developments in this area. In particular, we show how to prove this conjecture for reducts of certain homogeneous hypergraphs.
This is a joint work with Antoine Mottet and Michael Pinsker