Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-091 | 29th September 2004 00:00

Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

RSS-Feed




TR04-091
Authors: Ondrej Klíma, Pascal Tesson, Denis Thérien
Publication: 3rd November 2004 21:15
Downloads: 1155
Keywords: 


Abstract:

We consider the problem of testing whether a given system of equations
over a fixed finite semigroup S has a solution. For the case where
S is a monoid, we prove that the problem is computable in polynomial
time when S is commutative and is the union of its subgroups
but is NP-complete otherwise. When S is a monoid or a
regular semigroup, we obtain similar dichotomies for the restricted
version of the problem where no variable occurs on the right-hand side
of each equation.



ISSN 1433-8092 | Imprint