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.