FINITE MONOIDS - FROM WORD TO CIRCUIT EVALUATION

The problem of evaluating a circuit whose wires carry values from a fi nite 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 ti es between evaluating circuits over monoids and the structure of the c omplexity class P are exhibited. It is shown that circuit evaluation i n the case of any nonsolvable monoid is P complete, while circuits ove r solvable monoids can be evaluated in DET subset of or equal to NC2. Then the case of aperiodic monoids is completely elucidated: their cir cuit evaluation problems are either in AC(0) or L- or NL-complete, dep ending on the precise algebraic properties of the monoids. Finally, it is shown that the evaluation of circuits over the cyclic group Z(q) f or fixed q greater than or equal to 2 is complete for the logspace cou nting class co-MOD(q)L, that the problem for p-groups (p a prime) is c omplete for MOD(p)L, and that the more general case of nilpotent group s of exponent q belongs to the Boolean closure of MOD(q)L.