We consider circuits and expressions whose gates carry out multiplication i
n a nonassociative groupoid such as a quasigroup or loop. We define a class
we call the polyabelian groupoids, formed by iterated quasidirect products
ol Abelian groups. We show that a quasigroup can express arbitrary Boolean
functions if and only if it is not polyabelian, in which case its Expressi
on Evaluation and Circuits Value problems are NC1-complete and P-complete,
respectively. This is not true for groupoids in general, and we give a coun
ter-example. We show that Expression Evaluation is also NC1-complete if the
groupoid has a nonsolvable multiplication group or semigroup, but is in TC
0 if the groupoid both is polyabelian and has a solvable multiplication sem
i-group. e.g., for a nilpotent loop or group. Interestingly, in the nonasso
ciative case. the criteria for making Circuit Value P-complete and for maki
ng Expression Evaluation NC1-complete-nonpolyabelianness and nonsolvability
of the multiplication group are different. Thus, earlier results about the
role of solvability in complexity generalize in several different ways. (C
) 2000 Academic Press.