Decision Problems in Computational Topology

Recognizing whether two closed d-dimensional triangulated manifolds M1 and M2 are homeomorphic

d=4
 undecidable, even for some fixed M3 [Markov 1960]
d=3
 open
d=2
 decidable (easy)
 linear time

Do the problems become simpler if the manifolds are embedded in Rd+1?

Recognizing whether a d-dimensional manifold M1 is homeomorphic to the d-sphere

d=5

d=4

d=3
 decidable [Rubinstein 1994]
 some complexity results [Casson]
d=2
 decidable (easy)
 linear time
All closed 3-manifolds can be triangulated

Knots and links in R3

Recognition of the unknot (the trivial knot)
 decidable [Haken 1961, and other algorithms]
in NP [Hass, Lagarias, Pippenger, JACM 64 (1999), 185-211]
Deciding wheter two knots are equivalent
 decidable [Waldhausen 1978, Hemion 1979 and 1992]
Deciding whether two knots are unlinked (can be split)
 decidable [Haken 1961, Schubert 1961]
 in NP [Hass, Lagarias, Pippenger, JACM 64 (1999), 185-211]