Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization
Skip to main content
eScholarship
Open Access Publications from the University of California

Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization

  • Author(s): Kuperberg, Greg
  • et al.

Published Web Location

https://arxiv.org/pdf/1508.06720.pdf
No data is associated with this publication.
Abstract

In this paper we prove two results, one folklore and the other new. The folklore result, which goes back to Thurston, 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 makes essential use of normal surface theory, Mostow rigidity, and improved bounds on the computational complexity of solving algebraic equations.

Item not freely available? Link broken?
Report a problem accessing this item