Kuperberg (Pacific J. Math. 2019) proved that the oriented homeomorphism problem for closed, triangulated 3-manifolds lies in the elementary-recursive (ER) complexity class, and in Section 9 of that paper posed the effectivity questions his theorem leaves open: (9.1) whether Perelman's Ricci-flow-with-surgery proof of geometrization can itself be simulated in ER; (9.2) whether every closed hyperbolic 3-manifold has a finite-sheeted Haken cover computable in ER, i.e. whether Agol's virtual Haken theorem is effectively realizable; (9.3) whether any two triangulations of a closed 3-manifold have a mutual refinement computable in ER; and where the homeomorphism problem sits in the finer hierarchy (NP, PSPACE, EXP) strictly inside ER.

Background

A triangulation of a 3-manifold is a finite simplicial complex built by gluing tetrahedra; its size is its number of tetrahedra. The homeomorphism problem for closed 3-manifolds asks for an algorithm that decides whether two given triangulations determine homeomorphic (here, orientation-preservingly homeomorphic) closed 3-manifolds. By a theorem of Markov, the analogous problem is undecidable in every dimension at least 4, so dimension three is the decidable frontier. Decidability there comes from the geometrization theorem of Thurston, proved by Perelman: every closed 3-manifold splits along embedded spheres and incompressible tori into pieces, each carrying one of eight model geometries, the generic geometry being hyperbolic. Perelman's proof evolves an arbitrary Riemannian metric by Ricci flow with surgery, a parabolic PDE that excises regions developing singularities and continues the flow, terminating in the geometric decomposition (Perelman, arXiv:math/0303109).

On the complexity side, a function is elementary-recursive (ER) if it is bounded by a tower of exponentials of some fixed height in the input size; the class ER contains the standard classes P, NP, PSPACE, and EXP. Kuperberg's Theorem 1.2 (2019) states that the oriented homeomorphism problem for closed 3-manifolds is in ER. The proof assumes only the statement of geometrization, not any particular proof of it, and combines normal surface theory (a technique that encodes embedded surfaces in a triangulated 3-manifold as lattice points satisfying linear equations and inequalities), Mostow rigidity (the theorem that a closed hyperbolic 3-manifold of dimension at least 3 has a unique hyperbolic metric, so any homotopy equivalence is homotopic to an isometry), and ER bounds on solving systems of polynomial equations.

Section 9 of the same paper records what this does not settle. First, the effective content of Perelman's construction: Conjecture 9.1 asks whether Ricci flow with surgery on a closed Riemannian 3-manifold can be accurately simulated in ER, which would place Perelman's proof of geometrization itself in ER. Second, the effective content of virtual Haken theory: Agol's virtual Haken theorem (2013) states that every closed hyperbolic 3-manifold has a finite-sheeted cover containing an embedded incompressible (fundamental-group-injective) surface, i.e. a Haken cover; the proof passes through surface-subgroup existence and virtually special cube-complex techniques whose bounds are non-explicit, and Conjecture 9.2 asks whether such a cover can be produced in ER. Third, triangulation equivalence: by a classical theorem of Pachner, two triangulations of the same PL manifold share a common subdivision (a mutual refinement) if and only if they are related by a finite sequence of local bistellar (Pachner) moves; Conjecture 9.3 asks whether a mutual refinement of any two triangulations of a closed 3-manifold is computable in ER. Kuperberg's algorithm for Theorem 1.2 does not yield this, because in the hyperbolic case it only establishes a simplicial homotopy equivalence and then invokes Mostow rigidity instead of refining triangulations. Finally, the paper asks where the homeomorphism problem lies among the familiar qualitative classes strictly inside ER, noting that the author does not know where a careful version of the proof of Theorem 1.2 would land in the hierarchy P, NP, PSPACE, EXP, and so on.

Relevant prior work on triangulation moves predates the conjectures: Mijatovic (2003-2005) obtained explicit tower-of-exponentials bounds on Pachner moves for triangulations of the 3-sphere and of Seifert fibered manifolds, which Kuperberg cites as establishing ER mutual refinements in those classes, and a primitive-recursive (not ER) mutual refinement for fiber-free Haken manifolds; these supply the inputs behind the implications Kuperberg observes among his conjectures.

Problem Statement

Settle the elementary-recursive (ER) effectivity of the classification of closed 3-manifolds, as posed in Section 9 of Kuperberg (2019), in full generality and with no restriction of model class, dimension convention, or answer form beyond the source:

  1. (Conjecture 9.1) Prove or refute: if MM is a closed, Riemannian 3-manifold, then Ricci flow with surgery on MM can be accurately simulated in ER; equivalently, Perelman's proof of geometrization can be placed in ER, the simulation yielding the geometric decomposition within an elementary-recursive resource bound in the size of the description of MM.

  2. (Conjecture 9.2) Prove or refute: every closed, hyperbolic 3-manifold NN has a finite-sheeted Haken covering space that is computable in ER, i.e. an algorithm with elementary-recursive running time outputs an explicit description of a finite cover of NN containing an embedded incompressible surface.

  3. (Conjecture 9.3) Prove or refute: any two triangulations of a closed 3-manifold MM have a mutual refinement (a common subdivision) computable in ER.

  4. Determine where the oriented homeomorphism problem for closed, triangulated 3-manifolds lies in the finer complexity hierarchy strictly inside ER, i.e. the tightest class (among P, NP, PSPACE, EXP, and the like) that contains it.

The components form one program: Kuperberg's Theorem 1.2 places the homeomorphism problem in ER while treating geometrization as an oracle-like existence statement, and components 1-3 ask for the effective content of the three existence inputs behind that theorem (geometric decomposition via Ricci flow, virtual Haken covers, and triangulation equivalence), with component 4 asking how far the resulting bounds can be sharpened. Each component is nevertheless independent; results restricted to geometric triangulations, fixed topology classes, or finite families do not close the corresponding conjecture.

References

  1. Greg Kuperberg, Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization, Pacific Journal of Mathematics 301(1) (2019) 189-241, DOI 10.2140/pjm.2019.301.189, arXiv:1508.06720, https://doi.org/10.2140/pjm.2019.301.189
  2. Grisha Perelman, Ricci flow with surgery on three-manifolds, preprint (2003), arXiv:math/0303109, https://arxiv.org/abs/math/0303109
  3. Ian Agol, The virtual Haken conjecture, with an appendix by Ian Agol, Daniel Groves and Jason Manning, Documenta Mathematica 18 (2013) 1045-1087, DOI 10.4171/dm/421, arXiv:1204.2810, https://doi.org/10.4171/dm/421
  4. Udo Pachner, P.L. homeomorphic manifolds are equivalent by elementary shellings, European Journal of Combinatorics 12(2) (1991) 129-145, DOI 10.1016/S0195-6698(13)80080-7, https://doi.org/10.1016/S0195-6698(13)80080-7
  5. Peter Scott, Hamish Short, The homeomorphism problem for closed 3-manifolds, Algebraic & Geometric Topology 14 (2014) 2431-2444, DOI 10.2140/agt.2014.14.2431, https://doi.org/10.2140/agt.2014.14.2431
  6. Aleksandar Mijatovic, Simplifying triangulations of S^3, Pacific Journal of Mathematics 208(2) (2003) 291-324, arXiv:math/0008107, https://arxiv.org/abs/math/0008107
  7. Aleksandar Mijatovic, Triangulations of Seifert fibred manifolds, Mathematische Annalen 330(2) (2004) 235-273, arXiv:math/0301246, https://arxiv.org/abs/math/0301246
  8. Aleksandar Mijatovic, Triangulations of fibre-free Haken 3-manifolds, Pacific Journal of Mathematics 219(1) (2005) 139-186, arXiv:math/0306116, https://arxiv.org/abs/math/0306116
  9. Marc Lackenby, Algorithms in 3-manifold theory, survey (2020), arXiv:2002.02179, https://arxiv.org/abs/2002.02179
  10. Joe Scull, The Homeomorphism Problem For Hyperbolic Manifolds I, preprint (2021), arXiv:2108.00779, https://arxiv.org/abs/2108.00779
  11. Marc Lackenby, 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
  12. Adele Jackson, Recognition of Seifert fibered spaces with boundary is in NP, Mathematische Annalen 391(1) (2025) 309-361, DOI 10.1007/s00208-024-02920-x, arXiv:2306.04612, https://doi.org/10.1007/s00208-024-02920-x
  13. Tejas Kalelkar, Advait Phanse, An upper bound on Pachner moves relating geometric triangulations, Discrete & Computational Geometry 66 (2021) 809-830, DOI 10.1007/s00454-021-00283-7, arXiv:1902.02163, https://doi.org/10.1007/s00454-021-00283-7
  14. Tejas Kalelkar, Sriram Raghunath, Bounds on Pachner moves and systoles of cusped 3-manifolds, Algebraic & Geometric Topology 22 (2022) 2951-2996, DOI 10.2140/agt.2022.22.2951, arXiv:2007.02781, https://doi.org/10.2140/agt.2022.22.2951
  15. Stephan Tillmann, Anastasiia Tsvietkova, Moving between 3-manifold triangulations is NP-hard, preprint (2026), arXiv:2606.14413, https://arxiv.org/abs/2606.14413
  16. Stefan Friedl, Tobias Hirsch, Marc Kegel, The Unsolvability of the Homeomorphism Problem, expository preprint (2026), arXiv:2603.23630, https://arxiv.org/abs/2603.23630