The word problem and growth of groups
The word problem and growth of groups
Let $\mathrm{WP}_G$ denote the word problem in a finitely generated group $G$. We consider the complexity of $\mathrm{WP}_G$ with respect to standard deterministic Turing machines. Let $\mathrm{DTIME}_k(t(n))$ be the complexity class of languages solved in time $O(t(n))$ by a Turing machine with $k$ tapes. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_1(n\log n)$ if …