d=4 
undecidable, even for some fixed M3 [Markov 1960] 

d=3 
open 

d=2 
decidable (easy) 
linear time 
d=5 

d=4 

d=3 
decidable [Rubinstein 1994] 
some complexity results [Casson] 
d=2 
decidable (easy) 
linear time 
Recognition of the unknot (the trivial knot) 
decidable [Haken 1961, and other algorithms] 
in NP [Hass, Lagarias, Pippenger, JACM 64 (1999),
185211] 
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),
185211] 