Finite monoids: From word to circuit evaluation

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 NC1, 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 subset of or equal to NC2. 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 Z(q) for fixed q greater than or equal to 2 is complete for the logspace counting class co-MOD(q)L, that the problem for p-groups (p a prime) is complete for MOD(p)L, and that the more general case of nilpotent groups of exponent q belongs to the Boolean closure of MOD(q)L.