Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-059 | 9th May 2005 00:00

Tractable Clones of Polynomials over Semigroups

RSS-Feed




TR05-059
Authors: Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien
Publication: 31st May 2005 13:46
Downloads: 1873
Keywords: 


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.



ISSN 1433-8092 | Imprint