Algebra Seminar talk
2022-10-14
Tomas Nagy
The Bodirsky-Pinsker conjecture for reducts of hypergraphs
Abstract:
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