The problem of evaluating a circuit whose wires carry values from a finite monoid M and whose gates perform the monoid operation provides a meaningful generalization to the well-studied problem of evaluating a word over M. Evaluating words over monoids is closely tied to the fine structure of the complexity class $NC^1$, and in this paper analogous ties between evaluating circuits over monoids and the structure of the complexity class P are exhibited. It is shown that circuit evaluation in the case of any nonsolvable monoid is P complete, while circuits over solvable monoids can be evaluated in $DET \subseteq NC^2$. Then the case of aperiodic monoids is completely elucidated: their circuit evaluation problems are either in $AC^0$ or L- or $NL$-complete, depending on the precise algebraic properties of the monoids. Finally, it is shown that the evaluation of circuits over the cyclic group ${\Bbb Z}_q$ for fixed $q \geq 2$ is complete for the logspace counting class $co$-$MOD_qL$, that the problem for p-groups (p a prime) is complete for $MOD_pL$, and that the more general case of nilpotent groups of exponent q belongs to the Boolean closure of $MOD_qL$.

The problem of testing membership in aperiodic or “group-free” transformation monoids is the natural counterpart to the well-studied membership problem in permutation groups. The class A of all finite aperiodic monoids and the class G of all finite groups are two examples of varieties , the fundamental complexity units in terms of which finite monoids are classified. The collection of all varieties V forms an infinite lattice under the inclusion ordering, with the subfamily of varieties that are contained in A forming an infinite sublattice. For each V ⊆ A , the associated problem MEMB( V ) of testing membership in transformation monoids that belong to V , is considered. Remarkably, the computational complexity of each such problem turns out to look familiar. Moreover, only five possibilities occur as V ranges over the whole aperiodic sublattice: With one family of NP-hard exceptions whose exact status is still unresolved, any such MEMB( V ) is either PSPACE-complete, NP-complete, P-complete or in AC 0 . These results thus uncover yet another surprisingly tight link between the theory of monoids and computational complexity theory.