Algebra Seminar talk
The Bodirsky-Pinsker conjecture for reducts of hypergraphs, part 2
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.