(Quasi)-Identities in polymorphism clones and their application to constraint satisfaction (with infinite domains)

The CSP dichotomy conjecture (by Feder and Vardi) states that a \(\text{CSP}(B)\) for finite structures \(B\) is NP-complete or tractable. The dichotomy conjecture has been proven independently by Bulatov and Zhuk, who have shown in 2017 that \(\text{CSP}(B)\) is tractable if there exists a weak near-unanimity (WNU) polymorphism of \(B\). A WNU polymorphism is a \(k\)-ary function \(f\) (for some \(k \ge 3\)) preserving all relations in \(B\) and satisfying the identities \(f(y,x,\dots,x)=f(x,y,x,\dots,x)=\dots=f(x,\dots,x,y)\). There is no analogous general result for all CSPs with infinite domains, but there are similar results about deriving information about the tractability of \(\text{CSP}(B)\) for omega-categorical structures \(B\) from the existence of polymorphisms with certain properties.

In this talk we will first explain the algebraic approach to the complexity of constraint satisfaction, mention the most fundamental results for the finite case, and give some results about polymorphisms of omega-categorical structures whose automorphism group already is the symmetric permutation group.