Abstract:We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property {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 {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.
Keywords: loops, quasigroups, functional closure, solvability, quasidirect products, computational complexity
AMS Subject Classification: 17A01, 17-08, 68Q15, 68W30, 03G05