Proc. Mathematical Foundations of Computer Science (2000)
We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [GoldmannR1998] by exhibiting quasi-polynomial time algorithms for a subclass of solvable non-nilpotent groups and relate this question to a natural circuit complexity conjecture.
In the special case when M is aperiodic, we show that PROGRAM SATISFIABILITY is in P when the monoid belongs to the variety DA and is NP-complete otherwise. In contrast, we give an example of an aperiodic outside DA for which EQUATION SATISFIABILITY is computable in polynomial time and discuss the relative complexity of the two problems. We also study the closure properties of classes for which these problems belong to P and the extent to which these fail to form algebraic varieties.