11
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ mathoverflow.net/questions/53471/… $\endgroup$ – Carlo Beenakker Dec 7 '16 at 12:04
  • 2
    $\begingroup$ As Carlo suggested, look at "Are there any very hard unknots?", and in particular, Tom Mrowka's answer: it is in NP and in coNP, which many believe likely means polynomial-time. $\endgroup$ – Joseph O'Rourke Dec 7 '16 at 13:12
  • $\begingroup$ Yes, I have read that thread several times. The thing is, I think I have one. But I don't want to look like a complete fool by publishing it when "everyone knows" that there is no polynomial algorithm. Or look like a fool when "everyone knows" there's already a perfectly good polynomial algorithm $\endgroup$ – Peter Balch Dec 7 '16 at 14:27
  • 1
    $\begingroup$ I've thought a lot about this question on and off, and I don't know of an appropriate cost (there have been unverified claims before, but I wouldn't trust them). I can imagine a cost which might be monotonic, for example the rank of the complex of combinatorial knot floer homology for a grid diagram. But this is certainly not polynomial time to compute. $\endgroup$ – Ian Agol Dec 7 '16 at 17:50
  • 3
    $\begingroup$ @PeterBalch : If you have a polytime algorithm for untangling the unknot then that would be a major result. $\endgroup$ – Timothy Chow Dec 8 '16 at 1:18
7
$\begingroup$

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)

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A page describing the algorithm is here peterbalch.co.uk/UnknotPCB.html There's a link to download the exe at the bottom of the page. $\endgroup$ – Peter Balch Jan 3 '17 at 15:47
  • $\begingroup$ It seems that you have rediscovered Dynnikov's grid links. See Figures 1 and 2 of the paper arxiv.org/abs/math/0208153 . Dynnikov's result is not a polynomial-time recognition algorithm for the unknot, but it is remarkable! Lackenby has used (and is using?) this result in significant ways - eg for giving a polynomial bound on the number of Reidemeister moves required to simplify a diagram of the unknot. $\endgroup$ – Sam Nead Apr 11 '17 at 23:31
  • $\begingroup$ If you have any knots which you are unsure about, you could try feeding them to SnapPy (math.uic.edu/t3m/SnapPy) or you can ask here on MathOverflow. $\endgroup$ – Sam Nead Apr 11 '17 at 23:33
  • 1
    $\begingroup$ Thanks for your input. Perhaps it is equivalent but I don't see how. Dynnikov's links have "vias" in the sense that each "edge" is bounded by two vias. He tries to minimise "complexity" defined as the the number of vertical edges. (The number of vertical edges is half the number of vias.) So, yes, we're trying to minimise the same thing. But, as I understand it, his "moves" are not strictly monotonic. Some of his moves leave the complexity unchanged. $\endgroup$ – Peter Balch Apr 13 '17 at 20:42
  • $\begingroup$ I apologize - your diagrams look similar to his, but in fact they are (quite!) different. Also, you are correct that in his sequence of moves there may be very long plateaus. $\endgroup$ – Sam Nead Apr 14 '17 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.