Nearly-linear solution to the word problem for 3-manifold groups

2024/07/25 by Sisto, Alessandro, Zbinden, Stefanie
#FOS: Mathematics #Geometric Topology (math.GT) #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2407.18029

Abstract

We show that the word problem for any 3-manifold group is solvable in time O(nlog³ n). Our main contribution is the proof that the word problem for admissible graphs of groups, in the sense of Croke and Kleiner, is solvable in O(nlog n); this covers fundamental groups of non-geometric graph manifolds. Similar methods also give that the word problem for free products can be solved "almost as quickly" as the word problem in the factors.

Related

• The word problem for the mapping class group in quasi-linear time
• The Word Problem is Solvable for 3-free Artin groups in Quadratic Time
• The word problem for free groups cannot be solved in linear time*
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Recognizing geometric 3-manifold groups using the word problem