Is the homeomorphism problem for closed 3-manifolds in NP? NP recognition of the remaining Thurston geometries

Lackenby and Schleimer proved that deciding whether a closed 3-manifold is elliptic, meaning that it admits the spherical Thurston geometry, lies in the complexity class NP, and that naming an elliptic manifold by its Seifert data lies in FNP. They motivated this as a step into a largely uncharted landscape: the homeomorphism problem for closed orientable 3-manifolds given by triangulations is decidable via geometrisation and is known to be elementary recursive (Kuperberg), but it is not known to lie in NP, and recognition of the remaining Thurston geometries is likewise not known to lie in NP. This problem asks for the NP-membership status of the 3-manifold homeomorphism problem. The core question remains open: through 2026 only partial progress is known (Seifert fibered spaces with boundary in NP, conditional coNP-side results, bounded-runtime algorithms for hyperbolic homeomorphism).

Background

In low-dimensional topology, a compact 3-manifold is presented to a computer as a finite triangulation, a gluing table of $t$ tetrahedra, and $t$ is taken as the input size. The homeomorphism problem asks, given two such triangulations, whether the manifolds they define are homeomorphic. Two deep results shape what is known. First, Thurston's geometrisation conjecture, proved by Perelman, states that every closed orientable 3-manifold can be cut along essential spheres and tori into pieces, each carrying one of eight model geometries: spherical $S^3$ , Euclidean $E^3$ , hyperbolic $H^3$ , $S^2\times\mathbb{R}$ , $H^2\times\mathbb{R}$ , Nil, Sol, and the universal cover $\widetilde{\mathrm{SL}(2,\mathbb{R})}$ of the unit tangent bundle of the hyperbolic plane. A closed manifold is called elliptic if it carries the spherical geometry, equivalently if its fundamental group is finite and it is finitely covered by the 3-sphere. Second, Haken's theory of normal surfaces (surfaces in a triangulated 3-manifold that intersect every tetrahedron in a controlled finite set of triangles and quadrilaterals) makes the geometric decomposition effectively computable, so the homeomorphism problem is decidable. Kuperberg refined this by showing that the problem is elementary recursive, meaning the running time is bounded by a tower of exponentials of fixed height in the input size; this enormous bound remains the best known upper bound for the general problem.

The complexity class NP consists of decision problems whose YES instances admit certificates of length polynomial in the input size that can be checked in polynomial time; FNP is the analogous class for problems whose output is more complicated than a yes/no answer. Several recognition problems are known to lie in NP: recognizing the 3-sphere (Schleimer, with another proof by Ivanov, who also proved it for the solid torus), recognizing $T^2\times I$ and the twisted $I$ -bundle over the Klein bottle (Haraway and Hoffman), and, building on Kuperberg's polynomial-time algorithm for identifying which lens space a triangulation represents, the results of the source paper: recognizing that a closed 3-manifold is elliptic lies in NP, and producing its Seifert data, the combinatorial parameters specifying a Seifert fibration (a decomposition of the manifold into disjoint circles, each with a tubular neighbourhood that is a standard fibered solid torus), lies in FNP. The certificates cannot simply exhibit a finite cover homeomorphic to $S^3$ : the lens space $L(F_n,F_{n-1})$ (a manifold built by gluing two solid tori, with $F_n$ the $n$ -th Fibonacci number) has a triangulation with $n$ tetrahedra but universal cover of degree $F_n$ , exponential in $n$ . Instead, Lackenby and Schleimer prove that in the 86th iterated barycentric subdivision of any triangulation of a non-exceptional lens space, some loop in the one-skeleton has simplicial neighbourhood that is a Heegaard solid torus (a solid torus whose boundary, together with a complementary solid torus, gives a Heegaard splitting of the manifold), and this bounded-complexity witness drives the NP membership.

Against this background the frontier is explicit. The homeomorphism problem for closed orientable 3-manifolds is not known to lie in NP. Recognition is not known to lie in NP for the remaining geometries: for hyperbolic manifolds (where a certificate would have to encode an exact solution of the Thurston gluing equations, the polynomial equations defining a hyperbolic structure on a triangulation, and the algebraic numbers involved may have degree exponential in $t$ ), for Sol manifolds (torus bundles and semi-bundles), or for the closed Seifert geometries $E^3$ , $S^2\times\mathbb{R}$ , Nil, $H^2\times\mathbb{R}$ , and $\widetilde{\mathrm{SL}(2,\mathbb{R})}$ . Progress so far covers only the spherical case and manifolds with non-empty boundary, and on the complementary side the strongest results are conditional: Zentner proved that 3-sphere recognition lies in coNP (the class of decision problems whose complements lie in NP) assuming the generalised Riemann hypothesis, and Hoffman and Petersen proved that lens space recognition lies in coNP for inputs promised to be Seifert fibered. Scull has given a bounded-runtime (tower-of-exponentials) algorithm for the homeomorphism problem restricted to hyperbolic manifolds, and Lackenby and Purcell computed the triangulation complexity, the minimal number of tetrahedra, of elliptic and Sol manifolds up to a bounded factor, but neither gives NP membership.

Problem Statement

Let HOMEOMORPHIC be the decision problem whose input is a pair of finite triangulations, with a total of at most $t$ tetrahedra, of closed orientable 3-manifolds $M$ and $N$ , and which asks whether $M$ and $N$ are homeomorphic. The problem is to determine the NP-membership status of HOMEOMORPHIC: either exhibit a certificate of length bounded by a polynomial in $t$ , together with a polynomial-time verification procedure, for every pair of homeomorphic triangulations, or resolve the status negatively.

For each of the remaining Thurston geometries, whether recognition lies in NP is an open question, i.e. whether a triangulated compact orientable 3-manifold's admitting that geometry has a polynomial-size certificate checkable in polynomial time. Specifically: (1) hyperbolic recognition, for closed manifolds and for manifolds whose boundary consists of tori; (2) Sol recognition; (3) recognition of the closed Seifert geometries $E^3$ , $S^2\times\mathbb{R}$ , Nil, $H^2\times\mathbb{R}$ , and $\widetilde{\mathrm{SL}(2,\mathbb{R})}$ . A full positive resolution additionally requires certifying the composition and comparison of the geometric pieces (including isometry of hyperbolic pieces) within polynomial-size witnesses.

References

Marc Lackenby and Saul Schleimer, Recognising elliptic manifolds, Commentarii Mathematici Helvetici 101 (2025) 1-45, arXiv:2205.08802 (2022; v3 2025), doi:10.4171/cmh/597, https://arxiv.org/abs/2205.08802
Greg Kuperberg, Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization, Pacific Journal of Mathematics 301 (2019) 189-241, arXiv:1508.06720, doi:10.2140/pjm.2019.301.189, https://arxiv.org/abs/1508.06720
Saul Schleimer, Sphere recognition lies in NP, in Low-dimensional and Symplectic Topology, Proceedings of Symposia in Pure Mathematics 82, American Mathematical Society (2011), pp. 183-213, doi:10.1090/pspum/082/2768660, https://doi.org/10.1090/pspum/082/2768660
S. V. Ivanov, The computational complexity of basic decision problems in 3-dimensional topology, Geometriae Dedicata 131 (2008) 1-26, doi:10.1007/s10711-007-9210-4, https://doi.org/10.1007/s10711-007-9210-4
Greg Kuperberg, Identifying lens spaces in polynomial time, Algebraic & Geometric Topology 18 (2018) 767-778, arXiv:1509.02887, doi:10.2140/agt.2018.18.767, https://arxiv.org/abs/1509.02887
Robert Haraway III and Neil R. Hoffman, On the complexity of cusped non-hyperbolicity, arXiv:1907.01675 (2019; v3 2022), https://arxiv.org/abs/1907.01675
Adele Jackson, Recognition of Seifert fibered spaces with boundary is in NP, Mathematische Annalen 391 (2024) 309-361, arXiv:2306.04612, doi:10.1007/s00208-024-02920-x, https://arxiv.org/abs/2306.04612
Neil R. Hoffman and Kathleen L. Petersen, Small $\mathrm{PSL}(2,\mathbb{F})$ representations of Seifert fiber space groups, arXiv:2209.05478 (2022), https://arxiv.org/abs/2209.05478
Marc Lackenby and Jessica S. Purcell, The triangulation complexity of elliptic and sol 3-manifolds, Mathematische Annalen 390 (2024) 1623-1667, arXiv:2212.04683 (2022), doi:10.1007/s00208-023-02790-9, https://arxiv.org/abs/2212.04683
Raphael Zentner, Integer homology 3-spheres admit irreducible representations in $\mathrm{SL}(2,\mathbb{C})$ , Duke Mathematical Journal 167 (2018), no. 9, 1643-1712, arXiv:1605.08530 (2016), doi:10.1215/00127094-2018-0004, https://arxiv.org/abs/1605.08530
Joe Scull, The homeomorphism problem for hyperbolic manifolds I, arXiv:2108.00779 (2021), https://arxiv.org/abs/2108.00779
Peter Scott and Hamish Short, The homeomorphism problem for closed 3-manifolds, arXiv:1211.0264 (2012), https://arxiv.org/abs/1211.0264
Stephan Tillmann and Anastasiia Tsvietkova, Moving between 3-manifold triangulations is NP-hard, arXiv:2606.14413 (2026), https://arxiv.org/abs/2606.14413