Vol. 301, No. 1, 2019

Download this article
Download this article For screen
For printing
Recent Issues
Vol. 301: 1
Vol. 300: 1  2
Vol. 299: 1  2
Vol. 298: 1  2
Vol. 297: 1  2
Vol. 296: 1  2
Vol. 295: 1  2
Vol. 294: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Author Index
To Appear
 
Other MSP Journals
Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization

Greg Kuperberg

Vol. 301 (2019), No. 1, 189–241
DOI: 10.2140/pjm.2019.301.189
Abstract

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.

Keywords
geometrization, computational complexity, 3-manifold recognition
Mathematical Subject Classification 2010
Primary: 57M27, 57M50
Secondary: 68Q15
Milestones
Received: 16 June 2016
Revised: 23 August 2017
Accepted: 4 July 2018
Published: 16 September 2019
Authors
Greg Kuperberg
University of California, Davis
United States