Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction

Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove defi…