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.