ECCC-Report TR05-059https://eccc.weizmann.ac.il/report/2005/059Comments and Revisions published for TR05-059en-usTue, 31 May 2005 13:46:22 +0300
Paper TR05-059
| Tractable Clones of Polynomials over Semigroups |
Víctor Dalmau,
Ricard Gavaldà,
Pascal Tesson,
Denis Thérien
https://eccc.weizmann.ac.il/report/2005/059It 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.
Tue, 31 May 2005 13:46:22 +0300https://eccc.weizmann.ac.il/report/2005/059