The word problem and growth of groups

2024/03/17 by Ievgen Bondarenko, Bondarenko, Ievgen
Computer Science · Mathematics · #03D10 #20E08 #20F10 #68Q70 #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2403.11148

openalex publication_date 2024/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let WP_G denote the word problem in a finitely generated group G. We consider the complexity of WP_G with respect to standard deterministic Turing machines. Let 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 WP_G\inDTIME₁(nlog n) if and only if G is virtually nilpotent. We relate the complexity of the word problem and the growth of groups by showing that WP_G\not∈ DTIME₁(o(nlogγ(n))), where γ(n) is the growth function of G. We prove that WP_G\inDTIME_k(n) for strongly contracting automaton groups, WP_G\inDTIME_k(nlog n) for groups generated by bounded automata, and WP_G\inDTIME_k(n(log n)^d) for groups generated by polynomial automata. In particular, for the Grigorchuk group, WP_G\not\inDTIME₁(n^1.7674) and WP_G\inDTIME₁(n²).

Related

• The word problem for free groups cannot be solved in linear time*
• Complexity of some algorithmic problems in groups: a survey
• Numerical upper bounds on growth of automata groups
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• On the complexity of the word problem of the R. Thompson group V