Finite Monoids: From Word to Circuit Evaluation

Abstract

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$.