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.