I've found assertions that recognising the unknot is NP (but not explicitly NP hard or NP complete). I've found hints that people are looking for untangling algorithms that run in polynomial time (which implies they may exist). I've found suggestions that recognition and untangling require exponential time. (Untangling is a form of recognising.)
I suppose I'm asking whether there exists (1) a "diagram" of a knot, (2) a "cost" measure of the diagram, (3) a "move" which can be applied to the diagram, (4) the "move" always reduces the "cost", (5) the "move" can be selected and applied in polynomial time, (6) the "cost" can be calculated in polynomial time.
For instance, Reidemeister moves, fail on number (4) if the "cost" is number of crossings.
So what is the current status of the problem?