In what would seem to be a fantastic result, Marc Lackenby: A polynomial upper bound on Reidemeister moves, http://arxiv.org/abs/1302.0180 claims to prove that any diagram of the unknot with c crossings may be reduced to the trivial diagram using at most (231*c)^11 Reidemeister moves. He depends heavily on http://arxiv.org/abs/math/0208153 For two knots or links which are the same, what is an upper bound on the number of Reidemeister moves needed? Alexander Coward, Marc Lackenby: An upper bound on Reidemeister moves http://arxiv.org/abs/1104.1882 give a rather worse upper bound, namely, if n is the sum of the crossing numbers, then 2^(2^(2^(...(2^(n))...))) moves suffice, where the number of "2^" is 10^(1000000*n). Now that's what I call an upper bound, baby. It is known that the equivalence problem for manifolds is undecidable in all sufficiently large dimensions (in fact I think for 4D manifolds?) Kuperberg's claim that knottedness is in NP (under GRH) is here: http://arxiv.org/abs/1112.0845 and he says in 2002 Ian Agol claimed he'd proved this without requiring the GRH, but says his paper was never completely written up. But see thorem 2 in this: Ian Agol, Joel Hass, William P. Thurston: The Computational Complexity of Knot Genus and Spanning Area http://arxiv.org/abs/math/0205057 where it is claimed to be proven without need for GRH. Chad Musick in http://arxiv.org/abs/1110.2871 claimed unknottedness and unlinkedness was in P, but this paper "has been withdrawn until the proof can be clarified and verified."