Proceedings of the 12th Annual IEEE Conference on Computational Complexity (1997) 193-203, and Journal of Computer and System Sciences 60 (2000) 368-394.
We consider circuits and expressions whose gates carry out multiplication in a non-associative algebra such as loop. We define a class we call the polyabelian algebras, formed by iterated quasidirect products of Abelian groups. We show that a loop or 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 NC^1-complete and P-complete respectively. This is not true for algebras in general, and we give a counter-example.
We show that Expression Evaluation is also NC^1-complete if the algebra has a non-solvable multiplication semigroup, but is in TC^0 if it is both polyabelian and has a solvable multiplication semigroup.
Thus, in the non-associative case, earlier results about the role of solvability in circuit complexity generalize in several different ways.
Click here to download the (shorter) conference version