In Proc. Mathematical Foundations of Computer Science (MFCS) 2001.
We study the computational complexity of determining whether a systems of equations over a fixed finite monoid has a solution. In [GR99], it was shown that in the restricted case of groups the problem is tractable if the group is Abelian and NP-complete otherwise. We prove that in the general case, the problem is in P if the monoid is the direct product of an Abelian group and a commutative idempotent monoid, and is NP-complete if it does not divide such a monoid. In the restricted case where only constants appear on the right-hand side, we show that the problem is in P if the monoid is in the class R_1 join L_1, and that if an aperiodic monoid is outside this class, then it contains a submonoid for which this problem is NP-complete.
Furthermore interesting connections to the well-studied Constraint Satisfiability Problem are uncovered and exploited.