Bounded-runtime homeomorphism problem for finite-volume hyperbolic manifolds

For a class of manifolds, the homeomorphism problem asks for an algorithm that decides whether two given triangulations promised to represent manifolds of that class are homeomorphic. For closed hyperbolic 3-manifolds triangulated by at most $t$ tetrahedra, Scull (arXiv:2108.00779, 2021) gave a decision algorithm with runtime bounded by the explicit tower of exponentials $2^{2^{t^{O(t)}}}$ , improving on Kuperberg's elementary-recursive solution for all closed 3-manifolds, whose tower height was an unknown constant. The source paper's Future Work section names the finite-volume (cusped) case as the obvious next step and announces a sequel devoted to bounded-runtime homeomorphism for finite-volume hyperbolic $n$ -manifolds in all dimensions; that sequel has never appeared. This problem is open: decidability without any runtime bound is known via the isomorphism problem for toral relatively hyperbolic groups (Dahmani–Groves, 2008), and partial geometric building blocks exist (systole bounds for finite-volume manifolds, Pachner-move bounds for cusped geometric triangulations). The problem: for each $n \geq 3$ , give an algorithm deciding homeomorphism of triangulated complete hyperbolic $n$ -manifolds of finite volume in time bounded by a tower of exponentials of bounded height in the triangulation size.

Background

The homeomorphism problem for a class $\mathcal{C}$ of manifolds asks whether an algorithm exists which, given two finite triangulations and the promise that both represent manifolds in $\mathcal{C}$ , decides whether the underlying manifolds are homeomorphic. The problem behaves very differently by dimension. In dimensions 1 and 2 it is elementary. In every dimension $n \geq 4$ it is undecidable for general manifolds by a theorem of Markov (1958; see the expository account of Friedl, Hirsch and Kegel, arXiv:2603.23630, which gives a detailed modern proof). Dimension 3 is decidable but deep: all known algorithms rely on Thurston's geometrization conjecture, proved by Perelman, which decomposes a closed orientable 3-manifold into pieces each carrying one of eight model geometries, and the geometrically generic pieces are hyperbolic. A hyperbolic $n$ -manifold is a quotient of hyperbolic $n$ -space $\mathbb{H}^n$ (simply connected, complete, constant sectional curvature $-1$ ) by a discrete torsion-free group of isometries. Such a manifold may have finite Riemannian volume without being compact: its end neighborhoods, called cusps, are quotients of horoballs by virtually abelian groups ( $\mathbb{Z}^{n-1}$ up to finite index for $n \geq 3$ ), and the conjugacy classes of these cusp subgroups form the peripheral structure that any homeomorphism must respect. Cusped hyperbolic 3-manifolds include all hyperbolic knot and link complements in $S^3$ , and the finite-volume hyperbolic pieces of a general 3-manifold are exactly what remains to be handled after the Seifert-fibered pieces. A tower-of-exponentials bound is a function of the form $2^{2^{\cdot^{\cdot^{2^{f(t)}}}}}$ with the number of exponentiations (the height) fixed; an algorithm is elementary recursive if its runtime admits such a bound. Mostow–Prasad rigidity states that for $n \geq 3$ a complete finite-volume hyperbolic $n$ -manifold is determined up to isometry by its fundamental group, which is why the homeomorphism problem for this class reduces to an isomorphism problem for a special class of groups: for finite-volume manifolds the group is hyperbolic relative to the abelian cusp subgroups, and Dahmani and Groves solved the isomorphism problem for such toral relatively hyperbolic groups, giving decidability of homeomorphism for finite-volume hyperbolic $n$ -manifolds without any explicit runtime bound. Earlier 3-dimensional decidability algorithms (Sela's, via the isomorphism problem for hyperbolic groups; Scott and Short's alternative) likewise carried no complexity bound. Kuperberg (2019) proved that the homeomorphism problem for closed oriented 3-manifolds is elementary recursive, but his argument only establishes a tower bound whose height is some unknown universal constant; his open-problems section asks where a careful version of the algorithm lands in the hierarchy $P \subseteq PSPACE \subseteq EXP \subseteq \cdots$ . Scull (arXiv:2108.00779) settled the closed hyperbolic 3-dimensional case with an explicit tower bound: given two triangulations of closed hyperbolic 3-manifolds by at most $t$ tetrahedra, homeomorphism is decidable in time $2^{2^{t^{O(t)}}}$ . His method first constructs, from purely combinatorial input, a geometric triangulation (one whose simplices are totally geodesic) of bounded complexity, using Pachner moves (local bistellar modifications, which suffice to relate any two triangulations of the same PL manifold) and effective systole bounds (the systole is the shortest closed geodesic; its length must be bounded below in terms of $t$ ), and then compares the two manifolds as geometric objects via rigidity. The construction does not extend verbatim to finite-volume manifolds, because the fundamental domains are non-compact and the peripheral (cusp) structure must be recovered and matched. In the paper's Future Work the author calls the finite-volume case the obvious next step and states that the methods suggest the case of $n$ -dimensional hyperbolic manifolds, closed or finite volume, may be tractable, announcing a sequel devoted to the $n$ -dimensional finite-volume case; that sequel, listed as in preparation, has not appeared as of August 2026.

Problem Statement

For each $n \geq 3$ , give a bounded-runtime solution to the homeomorphism problem for complete hyperbolic $n$ -manifolds of finite volume — the extension that the source paper (Scull, arXiv:2108.00779) identifies as the obvious next step and as the subject of its unpublished sequel. Concretely: describe an algorithm which, given two finite triangulations, each consisting of at most $t$ top-dimensional simplices (ideal vertices allowed; a triangulation of the compact truncation may be supplied instead, with $t$ in either case counting the top-dimensional simplices of the supplied input) and carrying the promise that both triangulate complete hyperbolic $n$ -manifolds of finite volume, decides whether the two manifolds are homeomorphic, in runtime bounded by a tower of exponentials in $t$ whose height is a constant depending only on $n$ . The case $n = 3$ — cusped hyperbolic 3-manifolds, the class containing all hyperbolic knot and link complements and the finite-volume hyperbolic pieces of Thurston's geometric decomposition — is the central instance, and closed manifolds are the special case with empty cusp set. The algorithm takes as input solely the combinatorial data of the triangulations (no hyperbolic structure given), and must handle cusps, peripheral structure, and non-compact fundamental domains.

References

Joe Scull, The Homeomorphism Problem For Hyperbolic Manifolds I, arXiv:2108.00779 (2021), https://arxiv.org/abs/2108.00779
Greg Kuperberg, Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization, Pacific Journal of Mathematics 301(1):189-241 (2019), DOI: 10.2140/pjm.2019.301.189, https://doi.org/10.2140/pjm.2019.301.189 (also arXiv:1508.06720)
François Dahmani, Daniel Groves, The isomorphism problem for toral relatively hyperbolic groups, Publications Mathématiques de l'IHÉS 107:211-290 (2008), DOI: 10.1007/s10240-008-0014-3, https://doi.org/10.1007/s10240-008-0014-3
Z. Sela, The Isomorphism Problem for Hyperbolic Groups I, Annals of Mathematics (2) 141(2):217-283 (1995), DOI: 10.2307/2118520, https://doi.org/10.2307/2118520
Peter Scott, Hamish Short, The homeomorphism problem for closed 3-manifolds, Algebraic & Geometric Topology 14(4):2431-2444 (2014), DOI: 10.2140/agt.2014.14.2431, https://doi.org/10.2140/agt.2014.14.2431
Marc Lackenby, Algorithms in 3-manifold theory, arXiv:2002.02179 (2020), https://arxiv.org/abs/2002.02179
Joe Scull, Systole length in hyperbolic n-Manifolds, Geometriae Dedicata 216(6), article 68 (2022), DOI: 10.1007/s10711-022-00727-1, https://doi.org/10.1007/s10711-022-00727-1 (also arXiv:2102.00825)
Tejas Kalelkar, Sriram Raghunath, Bounds on Pachner moves and systoles of cusped 3-manifolds, Algebraic & Geometric Topology 22:2951-2996 (2022), DOI: 10.2140/agt.2022.22.2951, https://doi.org/10.2140/agt.2022.22.2951 (also arXiv:2007.02781)
Tejas Kalelkar, Advait Phanse, An Upper Bound on Pachner Moves Relating Geometric Triangulations, Discrete & Computational Geometry 66(3):809-830 (2021), DOI: 10.1007/s00454-021-00283-7, https://doi.org/10.1007/s00454-021-00283-7
Adele Jackson, Recognition of Seifert fibered spaces with boundary is in NP, Mathematische Annalen 391:309-361 (2024), DOI: 10.1007/s00208-024-02920-x, https://doi.org/10.1007/s00208-024-02920-x (also arXiv:2306.04612)
Marc Lackenby, Saul Schleimer, Recognising elliptic manifolds, arXiv:2205.08802 (2022), https://arxiv.org/abs/2205.08802
Stefan Friedl, Tobias Hirsch, Marc Kegel, The Unsolvability of the Homeomorphism Problem, arXiv:2603.23630 (2026), https://arxiv.org/abs/2603.23630
Jeffrey Bergfalk, Iian B. Smythe, Manifold classification from the descriptive viewpoint, arXiv:2512.24996 (2025), https://arxiv.org/abs/2512.24996
Henrique Ennes, Clément Maria, Hardness of computation of quantum invariants on 3-manifolds with restricted topology, Journal of Applied and Computational Topology 10(3), article 13 (2026), DOI: 10.1007/s41468-026-00245-z, https://doi.org/10.1007/s41468-026-00245-z (also arXiv:2503.02814)