Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization

DOI10.2140/PJM.2019.301.189MaRDI QIDQ2305331zbMATH OpenOpenAlexWikidataFDO

Authors Greg Kuperberg

Publication date 10 March 2020

Published in Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.06720

zbMATH Keywords

geometrization of 3-manifoldshomeomorphism problem for closed oriented 3-manifolds

Mathematics Subject Classification ID

General geometric structures on low-dimensional manifolds (57M50) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topology of 3-manifolds (57K30)

Abstract: In this paper we prove two results, one semi-historical and the other new. The semi-historical result, which goes back to Thurston and Riley, is that the geometrization theorem implies that there is an algorithm for the homeomorphism problem for closed, oriented, triangulated 3-manifolds. We give a self-contained proof, with several variations at each stage, that uses only the statement of the geometrization theorem, basic hyperbolic geometry, and old results from combinatorial topology and computer science. For this result, we do not rely on normal surface theory, methods from geometric group theory, nor methods used to prove geometrization. The new result is that the homeomorphism problem is elementary recursive, i.e., that the computational complexity is bounded by a bounded tower of exponentials. This result relies on normal surface theory, Mostow rigidity, and bounds on the computational complexity of solving algebraic equations.

Recommendations

• The homeomorphism problem for closed 3-manifolds
• Algorithmic topology and classification of 3-manifolds
• scientific article; zbMATH DE number 1134565
• scientific article; zbMATH DE number 2109306
• scientific article; zbMATH DE number 1133271

Cited in

(24)

• An upper bound on Pachner moves relating geometric triangulations
• An arithmetic analysis of closed surfaces
• Bounds on Pachner moves and systoles of cusped 3-manifolds
• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• Computing a link diagram from its exterior
• Systole length in hyperbolic \(n\)-manifolds
• Links with splitting number one
• Identifying lens spaces in polynomial time
• Poincaré's works leading to the Poincaré conjecture
• scientific article; zbMATH DE number 2109306 (Why is no real title available?)
• scientific article; zbMATH DE number 7236450 (Why is no real title available?)
• The homeomorphism problem for closed 3-manifolds
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• Algorithmic detection and description of hyperbolic structures on closed 3-manifolds with solvable word problem
• scientific article; zbMATH DE number 1342334 (Why is no real title available?)
• Practical bounds for a Dehn parental test
• Markov's theorem and algorithmically non-recognizable combinatorial manifolds
• An application of Poénaru's ``zipping theory
• An Implementation of the Bestvina–Handel Algorithm for Surface Homeomorphisms
• Finding non-orientable surfaces in 3-manifolds
• A criterion for homeomorphism between closed Haken manifolds
• Recognition of Seifert fibered spaces with boundary is in NP
• Around 3-manifold groups
• Some conditionally hard problems on links and 3-manifolds

This page was built for publication: Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2305331)