Abstract:
It is well known that coset-generating relations lead to tractable constraint satisfaction problems. These are precisely the relations closed under the operation $xy^{-1}z$ where the multiplication is taken in some finite group. Bulatov et al. have on the other hand shown that any clone containing the multiplication of some ``block-group'' (a particular class of semigroups) also yields a tractable CSP. We consider more systematically the tractability of $CSP(\Gamma)$ when $\Gamma$ is a set of relations closed under operations that are expressible as polynomials over a finite semigroup. In particular, we unite the two results above by showing that if $S$ is a block-group of exponent $\omega$ and $\Gamma$ is a set of relations over $S$ preserved by the operation defined by the polynomial $f(x,y,z) = xy^{\omega -1}z$ over $S$, then $CSP(\Gamma)$ is tractable. We show one application of this result by reproving an upper bound by Klima et al. on the complexity of solving systems of equations over certain block-groups. We show that if $S$ is a commutative semigroup and $\cC$ is an idempotent clone consisting of polynomials over $S$, then $\cC$ is tractable iff it contains the polynomial $xy^{\omega -1}z$. If $S$ is a nilpotent group, we show that a clone of polynomials over $S$ is tractable iff it contains a Malt'sev operation, and conjecture that this holds for all groups.