11

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

Peter Balch
  • 161
  • 2
    http://mathoverflow.net/questions/53471/are-there-any-very-hard-unknots – Carlo Beenakker Dec 07 '16 at 12:04
  • 2
    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. – Joseph O'Rourke Dec 07 '16 at 13:12
  • 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 – Peter Balch Dec 07 '16 at 14:27
  • 1
    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. – Ian Agol Dec 07 '16 at 17:50
  • Just recently I was similarly wondering about the popular "untangle" game... Is there more than just a superficial similarity between the two problems? (The goal of the game is to untangle a planar graph.) – Yaakov Baruch Dec 07 '16 at 20:01
  • 3
    @PeterBalch : If you have a polytime algorithm for untangling the unknot then that would be a major result. – Timothy Chow Dec 08 '16 at 01:18

3 Answers3

7

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)

Community
  • 1
Carlo Beenakker
  • 177,695
7

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.

Ian Agol
  • 66,821
5

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.

Peter Balch
  • 161
  • 1
    A page describing the algorithm is here

    http://www.peterbalch.co.uk/UnknotPCB.html

    There's a link to download the exe at the bottom of the page.

     – Peter Balch Jan 03 '17 at 15:47
  • It seems that you have rediscovered Dynnikov's grid links. See Figures 1 and 2 of the paper https://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. – Sam Nead Apr 11 '17 at 23:31
  • If you have any knots which you are unsure about, you could try feeding them to SnapPy (https://www.math.uic.edu/t3m/SnapPy/) or you can ask here on MathOverflow. – Sam Nead Apr 11 '17 at 23:33
  • 1
    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.

     – Peter Balch Apr 13 '17 at 20:42
  • 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. – Sam Nead Apr 14 '17 at 07:14
  • My other comment stands however -- if you find some difficult unknots, then there are several people here (including myself!) who would be interested in seeing them. Here is a paper that lists several - see in particular figure 27: "Algorithmic simplification of knot diagrams: new moves and experiments" by Carlo Petronio and Adolfo Zanellati. – Sam Nead Apr 14 '17 at 07:17