TR05-059 Authors: Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

Publication: 31st May 2005 13:46

Downloads: 1251

Keywords:

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.