|
Abstract : |
Abstract. We consider circuits and expressions whose gates carry out multiplication in a non-associative algebra such as a quasigroup or loop. We define a class we call the polyabelian algebras, 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 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 group or semigroup, but is in TC, |
