The word problem for 3-manifold groups is solvable: given a based loop $\gamma$ in $M^3$ there is an algorithm to decide whether $\gamma$ bounds a disk.


What kinds of quantitative results are known about this problem? Specifically, what are the known best upper bound estimates for the time and space complexity of these algorithms?


Suppose we use a triangulation as a genie, are there any results like the following? If $(M,T)$ is a closed 3-manifold $M$ and a triangulation $T$ of $M$ then there exists a PL loop $\gamma$ in $M$ such that if $T'$ is a triangulation of $M$ with a 2-skeleton containing a disk bounding the loop then the Pachner distance between the two triangulations $T$ and $T'$ must be greater than $e^l$, where $l$ is the length of $\gamma$.



Quantitative word problem for 3-manifold groups
Suppose that $M$ is a compact irreducible 3-manifold.


1. Assume that $M$ is neither a Nil nor a Sol-manifold. Then $G=\pi\_1(M)$ is automatic, which implies that $G$ has quadratic Dehn function and the word problem in $G$ is decidable in $O(n^2)$-time. If $M$ is a closed hyperbolic 3-manifold, then, of course, you get a linear estimate.


From the practical standpoint, finding an automatic structure on $G$ if $M$ is just given by its triangulation is a hard task. Even in the case when $M$ is a closed hyperbolic 3-manifold given by its triangulation, I do not think there are known explicit estimates of hyperbolicity constant for $G=\pi\_1(M)$ (with generating set, say, given by the triangulation) in terms of the triangulation. However, in principle, techniques for such estimates are available once you computed a Haken hierarchy (if $M$ is Haken). In general, this is an open problem how to extract geometric information about hyperbolic structure from a triangulation (besides estimating the hyperbolic volume), although in the last 10-15 years there was some progress in this direction.


2. If $M$ is a Nil or a Sol-manifold, the group $G=\pi\_1(M)$ embeds in $SL(3, Z)$. Hence, the WP in $G$ is decidable in (**correction**) $O(n^2)$-time: You just multiply integer matrices.
3. In the case of reducible oriented 3-manifolds, the fundamental group splits as a free product of fundamental groups of irreducible components and you obtain the same estimates on complexity of the WP as above.


Thus, the answer to your question is "at most quadratic and in **some** cases linear." The fact that the estimate is always quadratic suggests that there is a uniform proof of such a quadratic bound. I have no idea how this could/would work, apart from proving (Thurston's?) conjecture that fundamental groups of all compact 3-manifolds embed in $SL(N,Z)$ for some nonuniform $N$. The latter is known in "most" but not all cases.


Some references:


*Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P.*, Word processing in groups, Boston, MA etc.: Jones and Bartlett Publishers. xi, 330 p. (1992). [ZBL0764.20017](https://zbmath.org/?q=an:0764.20017).


*Aschenbrenner, Matthias; Friedl, Stefan; Wilton, Henry*, [**3-manifold groups**](http://dx.doi.org/10.4171/154), EMS Series of Lectures in Mathematics. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-154-5/pbk). xiv, 215 p. (2015). [ZBL1326.57001](https://zbmath.org/?q=an:1326.57001).


