Is there a polynomial-time algorithm for untangling the unknot? 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?
Thanks
Peter
 A: This 2012 report of "A fast branching algorithm for unknot recognition with experimental polynomial time behaviour" by B. Burton and M. Ozlen may well represent the current status of the problem:

It is a major unsolved problem as to whether unknot recognition - that is, testing whether a given closed loop in $R^3$ can be untangled to form a plain circle - has a polynomial time algorithm. 
  Here we present the first algorithm for unknot recognition that
  guarantees a conclusive result and, though still worst-case
  exponential in theory, behaves in practice like a polynomial-time
  algorithm under systematic, exhaustive experimentation.

(see also the discussion in this MO posting from 2013)
A: Recently, Marc Lackenby discussed a new algorithm for unknot recognition in a talk at the Newton Institute (see time around 1:03). He conjectures (but indicates at the time that it is work-in-progress) that his algorithm runs in quasi-polynomial time ($c^{\log c}$, where $c$ is the crossing number). In any case, his talk discusses the state of the art of the subject. More recently, he is announcing this as a conjecture, so presumably it is still a work in progress after 6 months. 
A: I seem to have a polynomial-time algorithm that untangles the unknot. But I suspect that hubris lurks around every corner in this game.
I'm pretty sure I can show that the algorithm runs in polynomial-time. But I now realise that I don't know if it is always able to simplify every tangle.
As always, the trick is to find a representation that makes it obvious what moves are legal and that has a measure of "cost" that decreases after every "move".
My attempt treats the knot as a printed circuit board. The measure of cost is the number of vias. Using vias to measure cost rather than "crossings" turns out to be advantageous. A legal move reroutes a track segment. Rerouting a single track segment is always legal. If the number of vias reaches zero, the tangle was a simple loop. 
I've written a Windows program that runs the algorithm and tried it with all the knots I can find on the web. It untangles all the knots that I know to be simple loops and doesn't untangle those I know to be truely knotted. Unfortunately, there are some published knots for which it's unclear whether they are knotted on not.
I'll try to upload a PDF and an EXE here if this forum allows it, otherwise I'll make a web page.
