# Algebra Seminar talk

2022-10-21

Tomáš **Nagy***The Bodirsky-Pinsker conjecture for reducts of hypergraphs, part 2*

Abstract:

We recall the definition of a constraint satisfaction problem (CSP) over
first-order reducts of finitely bounded homogeneous structures and the
Bodirsky-Pinsker dichotomy conjecture for CSPs of such structures. Such CSPs
can always be reduced to finite-domain CSPs but in some cases, the reduction
reduces a polynomial-time solvable CSP to an NP-complete one. We discuss when
does this reduction preserve the complexity and how is it used in the proofs of
the Bodirsky-Pinsker conjecture for certain CSPs.

Finally, we discuss a new proof of the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of certain hypergraphs. It turns out that the above-mentioned reduction works only for certain instances of such CSPs. This forces us to develop new algorithmic techniques to transform a CSP instance into an instance for which this reduction works.

This is a joint work with Antoine Mottet and Michael Pinsker.