Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization

DOI10.2140/PJM.2019.301.189zbMATH Open1434.57013arXiv1508.06720OpenAlexW1938784745WikidataQ127242002 ScholiaQ127242002MaRDI QIDQ2305331FDOQ2305331

Greg Kuperberg

Publication date: 10 March 2020

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

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.

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

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

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)

Cited In (20)

• An arithmetic analysis of closed surfaces
• An upper bound on Pachner moves relating geometric triangulations
• 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
• Poincaré's works leading to the Poincaré conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Practical bounds for a Dehn parental test
• Markov's theorem and algorithmically non-recognizable combinatorial manifolds
• An Implementation of the Bestvina–Handel Algorithm for Surface Homeomorphisms
• A criterion for homeomorphism between closed Haken manifolds
• Finding non-orientable surfaces in 3-manifolds
• Recognition of Seifert fibered spaces with boundary is in NP
• Some conditionally hard problems on links and 3-manifolds
• Around 3-manifold groups

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)