Circuits and Expressions with Non-Associative Gates
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 NC1-complete and P-complete respectively. This is not true for algebras in general, and we give a counter-example. <p> We show that EXPRESSION EVALUATION is also NC1-complete if the TC0 if the algebra is both polyabelian and has a solvable multiplication semigroup, e.g., for a nilpotent loop or group. <p> Thus, in the non-associative case, earlier results about the role of solvability in circuit complexity generalize in several different ways.
Year of publication: |
1997-01
|
---|---|
Authors: | Berman, Joshua ; Drisko, Arthur ; Lemieux, Francois ; Moore, Cristopher ; Therien, Denis |
Institutions: | Santa Fe Institute |
Saved in:
Saved in favorites
Similar items by person
-
Moore, Cristopher, (1995)
-
Quantum Circuits: Fanout, Parity, and Counting
Moore, Cristopher, (1999)
-
Closed-form Analytic Maps in One and Two Dimensions Can Simulate Turing Machines
Koiran, Pascal, (1996)
- More ...