We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property {\it Boolean completeness\/}. It is a generalization of functional completeness, and is intimately connected to the computational complexity of various questions about expressions, circuits, and equations defined over the loop. We say that a loop is {\it polyabelian\/} if it is an iterated affine quasidirect product of Abelian groups; polyabelianness coincides with solvability for groups, and lies properly between nilpotence and solvability for loops. Our main result is that a loop is Boolean-complete if and only if it is not polyabelian. Since groups are Boolean-complete if and only if they are not solvable, this shows that polyabelianness, for these purposes, is the appropriate generalization of solvability to loops.
@article{119201,
author = {Fran\c cois Lemieux and Cristopher Moore and Denis Th\'erien},
title = {Polyabelian loops and Boolean completeness},
journal = {Commentationes Mathematicae Universitatis Carolinae},
volume = {41},
year = {2000},
pages = {671-686},
zbl = {1051.20033},
mrnumber = {1800174},
language = {en},
url = {http://dml.mathdoc.fr/item/119201}
}
Lemieux, François; Moore, Cristopher; Thérien, Denis. Polyabelian loops and Boolean completeness. Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000) pp. 671-686. http://gdmltest.u-ga.fr/item/119201/
Quasigroups I, Trans. Amer. Math. Soc. 54 (1943), 507-519 and {Quasigroup II}, Trans. Amer. Math. Soc. 55 (1944), 401-419. (1943) | MR 0009962 | Zbl 0063.00039
Non-uniform automata over groups, Information and Computation 89 (1990), 109-132. (1990) | MR 1080845
Finite monoids and the fine structure of $NC^1$, Journal of the ACM 35 (1988), 941-952. (1988) | MR 1072406
Contributions to the theory of loops, Trans. Amer. Math. Soc 60 (1946), 245-354. (1946) | MR 0017288 | Zbl 0061.02201
A Survey of Binary Systems, Springer-Verlag, 1966. | MR 0093552 | Zbl 0141.01401
The complexity of computing over quasigroups, in Proc. 14th annual FST&TCS, 1994, pp.36-47. | MR 1318016 | Zbl 1044.68679
Quasigroups and Loops: Theory and Applications, Heldermann Verlag, 1990. | MR 1125806 | Zbl 0719.20036
Latin Squares and their Applications, English University Press, 1974. | MR 0351850
Proc. 14th Annual IEEE Conference on Computational Complexity, 1999, .
The Theory of Groups, Macmillan, 1959. | MR 0103215 | Zbl 0919.20001
Finite Groupoids and their Applications to Computational Complexity, Ph.D. Thesis, School of Computer Science, McGill University, Montréal, 1996.
A property of finite simple non-Abelian groups, Proc. Amer. Math. Soc. 16 (1965), 552-554. (1965) | MR 0175971 | Zbl 0132.26903
On minimal, locally finite varieties with permuting congruence relations, preprint, 1976.
Predicting non-linear cellular automata quickly by decomposing them into linear ones, Physica D 111 (1998), 27-41. (1998) | MR 1601494
Circuits and expressions with non-associative gates, to appear in J. Comput. System Sci.
Computational Complexity, Addison-Wesley, 1994. | MR 1251285 | Zbl 0833.68049
Quasigroups and Loops: Introduction, Heldermann Verlag, 1990. | MR 1125767 | Zbl 0715.20043
Families of recognizable sets corresponding to certain families of finite monoids, J. Pure Appl. Algebra 15 (1979), 305-318. (1979) | MR 0537503
Representing functions by words over finite semigroups, Université de Montréal, Technical Report #838, 1992.
Group Theory I., Springer-Verlag, 1982. | MR 0648772 | Zbl 0472.20001
Classification of finite monoids: the language approach, Theor. Comp. Sci. 14 (1981), 195-208. (1981) | MR 0614416
Clones in Universal Algebra, Les Presses de L'Université de Montréal, 1986. | MR 0859550 | Zbl 0603.08004
Solvable groups and loops, J. Algebra 180 (1996), 862-876. (1996) | MR 1379214 | Zbl 0853.20050