Satisfiability of Systems of Equations over Finite Monoids

Cristopher Moore, Pascal Tesson, and Denis Therien

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.

Click here to download

Cris Moore <>