Circuits and Expressions with Non-Associative Gates

Joshua Berman, Arthur Drisko, Francois Lemieux, Cristopher Moore and Denis Therien
Additional contact information
Cristopher Moore: http://www.santafe.edu/~moore

Working Papers from Santa Fe Institute

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 NC1-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 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.

Thus, in the non-associative case, earlier results about the role of solvability in circuit complexity generalize in several different ways.

Date: 1997-01
References: View complete reference list from CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:97-01-007

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().