Circuits and Expressions with Nonassociative Gates

摘要

We consider circuits and expressions whose gates carry out multiplication in a nonassociative groupoid such as a quasigroup or loop. We define a class we call the polyabelian groupoids, formed by iterated quasidirect 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 Circuits Value problems are NC1-complete and P-complete, respectively. This is not true for groupoids in general, and we give a counterexample. We show that Expression Evaluation is also NC1-complete if the groupoid has a nonsolvable multiplication group or semigroup, but is in TC0 if the groupoid both is polyabelian and has a solvable multiplication semigroup, e.g., for a nilpotent loop or group. Interestingly, in the nonassociative case, the criteria for making Circuit Value P-complete and for making 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.