Circuits and Expressions with Non-Associative Gates

We consider circuits and expressions whose gates carry outmultiplication in a non-associative algebra such as a quasi-group or loop. We define a class we call the polyabelian algebras, formed by iterated quasi-direct products of Abelian groups. We show that a quasigroup can express arbitrary Boolean functions if and only if it is not polyabelian, in which case its “expression evaluation” and “circuit value” problems are NC1-complete and P-complete respectively. This is not true for algebras in general, and we give a counterexample. We show that “ expression evaluation” is also NC1-complete if the TC0 of the algebra is both polyabelian and has a solvable multiplication semigroup, e.g., for a nilpotent loop or group. Thus, in the nonassociative case, earlier results about the role of solvability in circuit complexity generalize in several different ways.