ECCC-Report TR04-091https://eccc.weizmann.ac.il/report/2004/091Comments and Revisions published for TR04-091en-usWed, 03 Nov 2004 21:15:53 +0200
Paper TR04-091
| Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups |
Ondrej Klíma,
Pascal Tesson,
Denis Thérien
https://eccc.weizmann.ac.il/report/2004/091We 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.
Wed, 03 Nov 2004 21:15:53 +0200https://eccc.weizmann.ac.il/report/2004/091