Is the 3-manifold homeomorphism problem in NP?

The 3-manifold homeomorphism problem — given two finite triangulations of compact 3-manifolds, decide whether the underlying spaces are homeomorphic — is decidable by Thurston's geometrisation, and Kuperberg's elementary-recursive algorithm for closed orientable manifolds bounds its running time by a tower of exponentials of unspecified height; the problem is also known to be at least as hard as finite graph isomorphism. Whether it lies in NP, that is, whether homeomorphism admits polynomial-size certificates verifiable in polynomial time, is the overarching open question posed by Adele Jackson's 'Recognition of Seifert fibered spaces with boundary is in NP' (Math. Ann. 2024), which settled the first Seifert-fibered case with non-empty boundary. Recognition of closed Seifert fibered spaces — especially the small ones — polynomial certification of hyperbolicity for closed manifolds, and NP membership for the general problem all remain open.

Background

A triangulation encodes a compact 3-manifold finitely: a collection of tetrahedra with faces glued in pairs, so the manifold is recovered as the quotient space $|\mathcal{T}|$. Here "triangulation" is used in the standard sense conventional in low-dimensional topology (sometimes called a pseudo-triangulation): tetrahedra with affine gluing maps between their faces whose quotient is the given manifold, with distinct tetrahedra allowed to share vertices and edges. Inputs are promised to be genuine triangulations of compact 3-manifolds, so the manifold condition is taken as given rather than certified. The 3-manifold homeomorphism problem is the decision problem that takes two such triangulations $\mathcal{T}_1$ and $\mathcal{T}_2$ and asks whether $|\mathcal{T}_1|$ and $|\mathcal{T}_2|$ are homeomorphic. It occupies a special place in the topology of computation: for manifolds of dimension $n\geq 4$ the analogous problem is undecidable, meaning no algorithm solves it on all inputs (Markov, 1958), whereas in dimension 3 the proof of Thurston's geometrisation conjecture by Perelman implies decidability. Scott and Short gave an algorithmic account of this, Kuperberg proved that the problem is elementary recursive for closed orientable manifolds — solvable in time bounded by a tower of exponentials $2^{2^{\cdots^{t}}}$ of some fixed but unspecified height — and Lackenby showed the problem is at least as hard as finite graph isomorphism. In practice the problem is far easier than these bounds suggest — census projects have tabulated all closed orientable 3-manifolds triangulable with a small number of tetrahedra — so the gap between the theoretical bounds and practical computation is itself a central mystery. NP is the class of decision problems whose yes-instances admit certificates that can be checked in time polynomial in the input size; coNP is the class of problems whose no-instances admit such certificates, and FNP is the analogous class for search problems that must output a witness. Asking whether 3-manifold homeomorphism lies in NP asks whether, whenever two triangulations are homeomorphic, there is a polynomially bounded proof of this fact that a verifier can check in polynomial time — which would collapse the tower-of-exponentials bound to polynomial verification and provide short certificates for exactly the pairwise identifications that census projects currently make by ad hoc means. The standard attack follows geometrisation: a closed 3-manifold decomposes along essential (incompressible, not boundary-parallel) tori into its JSJ decomposition, after Jaco, Shalen and Johannson, and each piece carries one of Thurston's eight model geometries, of which the hyperbolic pieces and the Seifert fibered pieces are the essential cases. A Seifert fibered space is a 3-manifold foliated by circles, equivalently a circle bundle over a two-dimensional orbifold — a surface that may have cone points — classified up to homeomorphism by discrete Seifert data (base orbifold, singular-fiber parameters, and, in the closed case, an Euler number measuring how the circle fibers twist globally). The main tool for certifying such structure is normal surface theory, introduced by Haken: surfaces meeting every tetrahedron of a triangulation in triangles and squares, encoded by integer coordinates, so that searching for a useful surface becomes a finite integer search; a fundamental normal surface is one that is not the sum of other normal surfaces in the coordinate sense. Proving a recognition problem is in NP typically means exhibiting a fundamental normal surface of polynomially bounded complexity together with a polynomial-time check of its properties. This program has advanced piece by piece. Unknot recognition is in NP (Hass, Lagarias and Pippenger) and also in coNP (Lackenby's efficient certification of knottedness). Three-sphere recognition is in NP (independent work of Ivanov and Schleimer) and in coNP assuming the generalized Riemann hypothesis, the standard conjecture on the zeros of $L$-functions of number fields (Zentner). Recognition of elliptic manifolds — those with finite fundamental group, the $S^3$ geometry — is in NP, with naming, meaning deciding whether the input is the standard manifold with given classifying data, in FNP (Lackenby and Schleimer). Haraway and Hoffman certify non-hyperbolicity of cusped manifolds (those whose interior admits a complete finite-volume hyperbolic structure with torus cusps) in NP assuming only that three-sphere recognition is in coNP. Jackson proved that recognizing whether a triangulated 3-manifold admits a Seifert fibered structure with non-empty boundary is in NP, and that the corresponding naming problem is in NP $\cap$ coNP, by showing that every triangulation of such a space contains a fundamental horizontal surface — one transverse to the circle fibers — of small degree, and a complete collection of normal vertical annuli, meaning annuli foliated by fibers, of exponentially bounded total weight; recognition for closed Euclidean and Nil manifolds was handled in her thesis work. On the hyperbolic side, deciding hyperbolicity of a link from a diagram is in NP (announced by Baroni and Lackenby in 2025, building on Baroni's uniform polynomial-time classification of surface homeomorphisms and on fibredness detection in NP), and the homeomorphism problem restricted to closed hyperbolic 3-manifolds is decidable in time $2^{2^{t^{O(t)}}}$ in the number $t$ of tetrahedra (Scull). What the program has not reached: recognition of closed Seifert fibered spaces — particularly the small ones over a base $S^2$ with at most three cone points, where the horizontal surfaces and vertical annuli that power the boundary case can be absent and the fibration need not be unique, and the $\widetilde{SL_2}$ geometry (the universal cover of the Lie group $SL_2(\mathbb{R})$), carried by Seifert fibered spaces over hyperbolic base orbifolds with nonzero Euler number — as well as polynomial certification of hyperbolicity for closed manifolds and the assembly of piece certificates along the JSJ graph. Jackson's paper states the overarching question this leaves open: is the full 3-manifold homeomorphism problem in NP?

Problem Statement

The overarching question, posed explicitly in the source paper as its motivation: is the 3-manifold homeomorphism problem in NP? Concretely, for the decision problem that takes as input two finite triangulations $\mathcal{T}_1$ and $\mathcal{T}_2$ of compact 3-manifolds and asks whether the underlying spaces $|\mathcal{T}_1|$ and $|\mathcal{T}_2|$ are homeomorphic, does there exist a constant $c$ such that every yes-instance admits a certificate of length at most $N^c$ — where $N$ is the total encoding size of the two triangulations, that is, their number of tetrahedra together with the face-gluing data — that can be verified in polynomial time and that confirms the two underlying manifolds are homeomorphic, while no certificate is accepted for a no-instance? A complete answer must hold for arbitrary compact 3-manifolds — not only for hyperbolic manifolds, Seifert fibered manifolds, manifolds with non-empty boundary, or any other proper geometric subclass. (The source paper works under the convention that all 3-manifolds are compact and orientable; the question as posed here concerns arbitrary compact 3-manifolds, orientable or not, which is the general form of the homeomorphism problem.) In particular, any complete answer must cover the regimes the geometrisation-based program has not yet reached: closed Seifert fibered spaces (including small ones over $S^2$ with at most three cone points and $\widetilde{SL_2}$-geometry spaces), hyperbolic manifolds, and the assembly of geometric pieces along the JSJ decomposition. A rigorous proof, unconditional or under explicitly stated widely accepted hypotheses, that no polynomial-size polynomially-verifiable certificates exist settles the question negatively. Results for proper subclasses — for example, recognition of closed Seifert fibered spaces in NP — constitute meaningful partial progress but do not by themselves answer the question as stated.

References

1. Adele Jackson, 'Recognition of Seifert fibered spaces with boundary is in NP', Mathematische Annalen 391 (2024) 309-361. DOI: 10.1007/s00208-024-02920-x; arXiv:2306.04612. https://doi.org/10.1007/s00208-024-02920-x
2. Greg Kuperberg, 'Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization', Pacific Journal of Mathematics 301 (2019) 189-241. DOI: 10.2140/pjm.2019.301.189; arXiv:1508.06720. https://doi.org/10.2140/pjm.2019.301.189
3. A. Markov, 'The insolubility of the problem of homeomorphy', Doklady Akademii Nauk SSSR 121 (1958) 218-220. Zbl 0092.00702. https://zbmath.org/?q=an:3149985
4. Wolfgang Haken, 'Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten', Acta Mathematica 105 (1961) 245-375. DOI: 10.1007/BF02559591; Zbl 0100.19402. https://doi.org/10.1007/BF02559591
5. Peter Scott and Hamish Short, 'The homeomorphism problem for closed 3-manifolds', Algebraic & Geometric Topology 14 (2014) 2431-2444. DOI: 10.2140/agt.2014.14.2431; arXiv:1211.0264. https://doi.org/10.2140/agt.2014.14.2431
6. Marc Lackenby, 'Some Conditionally Hard Problems on Links and 3-Manifolds', Discrete & Computational Geometry 58 (2017) 580-595. DOI: 10.1007/s00454-017-9905-8. https://doi.org/10.1007/s00454-017-9905-8
7. Joel Hass, Jeffrey C. Lagarias and Nicholas Pippenger, 'The computational complexity of knot and link problems', Journal of the ACM 46 (1999) 185-211. DOI: 10.1145/301970.301971. https://doi.org/10.1145/301970.301971
8. 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
9. Saul Schleimer, 'Sphere recognition lies in NP', in Low-dimensional and Symplectic Topology, Proceedings of Symposia in Pure Mathematics 82, American Mathematical Society (2011) 183-213. DOI: 10.1090/pspum/082/2768660. https://doi.org/10.1090/pspum/082/2768660
10. Marc Lackenby, 'The efficient certification of knottedness and Thurston norm', Advances in Mathematics 387 (2021) 107796. DOI: 10.1016/j.aim.2021.107796. https://doi.org/10.1016/j.aim.2021.107796
11. Raphael Zentner, 'Integer homology 3-spheres admit irreducible representations in SL(2,C)', Duke Mathematical Journal 167 (2018) 1643-1712. DOI: 10.1215/00127094-2018-0004. https://doi.org/10.1215/00127094-2018-0004
12. Marc Lackenby and Saul Schleimer, 'Recognising elliptic manifolds', Commentarii Mathematici Helvetici 101 (2025) 1-45. DOI: 10.4171/cmh/597; arXiv:2205.08802. https://doi.org/10.4171/cmh/597
13. Robert Haraway III and Neil R. Hoffman, 'On the complexity of cusped non-hyperbolicity', arXiv:1907.01675 (2019). https://arxiv.org/abs/1907.01675
14. John Baldwin and Steven Sivek, 'On the complexity of torus knot recognition', Transactions of the American Mathematical Society 371 (2019) 3831-3855. DOI: 10.1090/tran/7394. https://doi.org/10.1090/tran/7394
15. Joe Scull, 'The Homeomorphism Problem For Hyperbolic Manifolds I', arXiv:2108.00779 (2021). https://arxiv.org/abs/2108.00779
16. Marc Lackenby, 'Certifying the hyperbolicity of knots and links', talk handout, Georgia International Topology Conference, 19 May 2025. https://people.maths.ox.ac.uk/lackenby/talk-knot-hyperbolicity-handout.pdf
17. Filippo Baroni, 'Uniformly polynomial-time classification of surface homeomorphisms', arXiv:2402.00231 (2024). https://arxiv.org/abs/2402.00231
18. Filippo Baroni, 'Fibredness of 3-manifolds is in NP', arXiv:2606.23284 (2026). https://arxiv.org/abs/2606.23284
19. Stephan Tillmann and Anastasiia Tsvietkova, 'Moving between 3-manifold triangulations is NP-hard', arXiv:2606.14413 (2026). https://arxiv.org/abs/2606.14413
20. Marc Lackenby, 'Incompressible surfaces, hierarchies and unknot recognition', arXiv:2607.23350 (2026). https://arxiv.org/abs/2607.23350