The word problem for free groups cannot be solved in linear time*

2022/02/10 by Alessandro Sisto, Sisto, Alessandro
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Mathematical Dynamics and Fractals #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2202.05787

openalex publication_date 2022/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

*by a standard (one-tape) Turing machine. It is well-known that the word problem for hyperbolic groups, whence in particular for free groups, can be solved in linear time. However, these algorithms run on machines more complicated than a standard Turing machine. By contrast, in this note we show that a standard Turing machine cannot solve the word problem for the free group on two generators in less than quadratic time.

Related

• Polynomial-time word problems
• Solving one variable word equations in the free group in cubic time
• The generalised word problem in hyperbolic and relatively hyperbolic groups
• The compressed word problem in relatively hyperbolic groups
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems