What is the complexity of the homeomorphism problem?

Homeomorphism Problems are the guiding problems of low-dimensional topology: Given two topological objects, determine whether or not they are homeomorphic to one another. A lot of topology is tangential to this problem- we may define invariants, investigate their properties, and prove relationships between them, but we rarely directly touch on the Homeomorphism Problem. Direct progress on the Homeomorphism Problem is a big deal!

I’m excited by a number of new and semi-new papers by Greg Kuperberg and collaborators. From my point of view, the most interesting of all is:

G. Kuperberg, Algorithmic homeomorphism of -manifolds as a corollary of geometrization, http://front.math.ucdavis.edu/1508.06720

This paper contains two results:

1) That Geometrization implies that there exists a recursive algorithm to determine whether two closed oriented –manifolds are homeomorphic.

2) Result (1), except with the words “elementary recursive” replacing the words “recursive”.

Result (1) is sort-of a well-known folklore theorem, and is essentially due to Riley and Thurston (with lots of subsections of it obtaining newer fancier proofs in the interim), but no full self-contained proof had appeared for it in one place until now. It’s great to have one- moreover, a proof which uses only the tools that were available in the 1970’s.

Knowing that we have a recursive algorithm, the immediate and important question is the complexity class of the best algorithm. Kuperberg has provided a worst-case bound, but “elementary recursive” is a generous computational class. The real question I think, and one that is asked at the end of the paper, is where exactly the homeomorphism problem falls on the heirarchy of complexity classes:

And whether the corresponding result holds for compact –manifolds with boundary, and for non-orientable –manifolds.