Cayley Linear-Time Computable Groups

Abstract

This paper looks at the class of groups admitting normal forms for which the right multiplication by a group element is computed in linear time on a multi-tape Turing machine. We show that the groups ${\mathbb{Z}}_2\wr {\mathbb{Z}}^2$, ${\mathbb{Z}}_2\wr {\mathbb{F}}_2$ and Thompson's group $F$ have normal forms for which the right multiplication by a group element is computed in linear time on a $2$-tape Turing machine. This refines the results previously established by Elder and the authors that these groups are Cayley polynomial-time computable.

Published in journal of Groups, Complexity, Cryptology