Abstract of Paper

Equation Satisfiability and Program Satisfiability for Finite Monoids
by David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson and Denis Therien

Abstract:

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 Goldmann and Russell 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.