This article is available for purchase or by subscription. See below.
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.
|
PDF Access Denied
We have not been able to recognize your IP address
54.89.70.161
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journal-recommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for
USD 40.00:
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
|
|