29
$\begingroup$
  • Kronheimer and Mrowka showed that the Khovanov homology detects the unknot.
  • Bar-Natan showed a program to compute the Khovanov homology fast: there was no rigorous complexity analysis of the algorithm, but it is estimated by Bar-Natan that the algorithm runs in time proportional to the square root of the number of crossings, so it is even less than linear in the number of crossings.

What I might understand from this, is that if we have:

  1. a proof for the correctness of Bar-Natan's algorithm

  2. a rigorous algorithm analysis showing the run time of the algorithm is polynomial or less

then we have a proof that the unknotting problem is in P.

I guess this is not really the case.

Is what I assume here true? if not, why? (maybe Bar-Natan's algorithm is not deterministic?)

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ "Bar-Natan showed a program to compute the Khovanov homology fast:" What is the reference for this, please? $\endgroup$
    – Sam Nead
    Commented Feb 27, 2016 at 10:49
  • 12
    $\begingroup$ $O(\sqrt{\text{crossings}})$ does not give time enough to even look at all the crossings. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Feb 27, 2016 at 16:31
  • 4
    $\begingroup$ The unknotting problem was solved a long time ago, it sounds like you are interested in polynomial-time unknot recognition. The exponential-time algorithms using normal surface theory have "most of the time" better than exponential run-times. To me it seems like this route is still the most enticing way to make progress on your problem. $\endgroup$
    – Ryan Budney
    Commented Feb 27, 2016 at 18:48
  • 3
    $\begingroup$ @MikeMiller: I have not read Bar Natan's paper. How does he determine his "usually" comment, is this a general statement or one derived by computing a few examples? If you give me an answer to that I should be able to answer your question. The "usually" for the normal surface / triangulation techniques is a very high probability for any knot you can draw in a short amount of time. And that conclusion is reached by computing for plenty of examples. If you have any complicated knots I'd be happy to run Regina over it. $\endgroup$
    – Ryan Budney
    Commented Feb 28, 2016 at 6:34
  • 3
    $\begingroup$ @MikeMiller: in practice it looks like a low-degree polynomial-time complexity. This is one paper that starts to quantify these observations: arxiv.org/abs/1110.6080 $\endgroup$
    – Ryan Budney
    Commented Feb 28, 2016 at 6:45

3 Answers 3

Reset to default
39
$\begingroup$

EDIT: Marc Lackenby has just announced a quasi-polynomial time algorithm. That is, given an $n$—crossing diagram, the algorithm takes $n^{O(\log(n))}$ time to either find a spanning disk (proving the knot is trivial) or a hierarchy (proving the knot is non-trivial).

PREVIOUS: A quick skim of the paper you linked to finds (on paragraph two of page two) comments by Bar-Natan suggesting that his improvement should take time $\exp({\sqrt{n}})$, beating the naive algorithm (taking time $\exp(n)$). That is, the improvement hopefully makes an exponential algorithm subexponential. He is not claiming a sublinear algorithm.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Sam, thanks for the answer, it appears I had a confusion about the values of C1 and b which are given in the introduction of Bar-Natan's paper. $\endgroup$
    – Omri
    Commented Feb 27, 2016 at 11:33
  • 8
    $\begingroup$ Two minor points to add to this: First, I assume it's $\exp(c\sqrt n)$ for some (possibly unknown) constant $c$, rather than necessarily $c=1$. And second, $\exp(c\sqrt n)$ is a typical time bound for many NP-complete problems on planar graphs (and knot diagrams are, essentially, planar graphs). So one shouldn't conclude that this subexponential time bound is low enough to make polynomial time likely — many other problems have the same bound and are still very unlikely to be polynomial. $\endgroup$
    – David Eppstein
    Commented Feb 29, 2016 at 5:44
  • 4
    $\begingroup$ Here's a link to the slides from Marc's talk: people.maths.ox.ac.uk/lackenby/quasipolynomial-talk.pdf $\endgroup$
    – Ian Agol
    Commented Feb 3, 2021 at 5:49
  • 2
    $\begingroup$ And the video of Marc's talk is here: video.ucdavis.edu/media/quasipolynomial-unknot/1_w3i5jvqi $\endgroup$
    – Mark Bell
    Commented Feb 18, 2021 at 10:42
41
$\begingroup$

To strengthen Sam Nead's answer, note that it is trivial to compute the Jones polynomial from the Khovanov homology. It is known that computing (or even approximating) the Jones polynomial is #P-hard:

  • Kuperberg, Greg, How hard is it to approximate the Jones polynomial?, Theory Comput. 11 (2015), 183–219. http://arxiv.org/pdf/0908.0512.pdf

  • Vertigan, Dirk, The computational complexity of Tutte invariants for planar graphs, SIAM J. Comput. 35 (2005), no. 3, 690–712.

Thus any approach along these lines will definitely not give an efficient algorithm for detecting the unknot (assuming standard complexity-theory conjectures).

Note that Jones conjectured that the Jones polynomial itself detects the unknot, but of course that still won't give an efficient algorithm.

Improve this answer
$\endgroup$
0
24
$\begingroup$

This isn't directly what you ask, but it's also worth noting that unknot detection is in $\text{NP} \cap \text{co-NP}$, that is, there are polynomial-checkable certificates that will show that either a knot is the unknot or that the knot is not the unknot. The $\text{NP}$ certificate uses normal surface theory:

  • Ian Agol, Joel Hass, William Thurston, The computational complexity of knot genus and spanning area. Trans. Amer. Math. Soc. 358 (2006), no. 9, 3821–3850.

The $\text{co-NP}$ certificate is currently conditional on the Generalized Riemann Hypothesis, and is based on finding representations of the knot group:

  • Greg Kuperberg, Knottedness is in NP, modulo GRH. Adv. Math. 256 (2014), 493–506.

(There ought to be another proof of the $\text{co-NP}$ result using normal surface theory and the notion of hierarchies. Ian Agol sketched that some time ago, but the details are difficult.)

The class $\text{NP} \cap \text{co-NP}$ is relatively small, and this gives reasons to believe that detecting the unknot is in $\text{P}$.

(I would have made this a comment, but I think it's too long for that.)

Improve this answer
$\endgroup$
5
  • 5
    $\begingroup$ Marc Lackenby has announced a proof that this problem is in co-NP independent of GRH. Marc Lackenby - The efficient certification of knottedness and Thurston norm - arxiv.org/abs/1604.00290 $\endgroup$
    – Neil Hoffman
    Commented Apr 6, 2016 at 0:47
  • 2
    $\begingroup$ I think it may be better to say being in the class $\text{NP}\cap\text{co-NP}$ gives reason to believe that detecting the unknot is not $\text{NP-complete}$, not that detecting the unknot is in $\text{P}$. Factoring is in $\text{NP}\cap\text{co-NP}$. $\endgroup$
    – Mark S
    Commented Dec 2, 2017 at 2:02
  • 1
    $\begingroup$ @MarkS, fair enough, but isn't also true that some people thing that factoring might also be in P? $\endgroup$
    – Dylan Thurston
    Commented Dec 3, 2017 at 7:43
  • $\begingroup$ Well, factoring is in $\text{BQP}$ - a quantum computer can factor in polynomial time. However, although I'm not sure I would understand fully, I believe quantum computers are not known to give a speed-up on knottedness, and through Kuperberg above, this may be unlikely. A "quantum money" scheme has been constructed based on this theoretical difficulty. Also, if $\text{P}\ne\text{NP}$, then there must be problems intermediate between $\text{P}$ and $\text{NP}$, and unknotting may be a good candidate. $\endgroup$
    – Mark S
    Commented Dec 3, 2017 at 17:52
  • 1
    $\begingroup$ Whereas, if a problem in $\text{NP}\cap\text{co-NP}$ or $\text{AM}\cap\text{co-AM}$ were $\text{NP-complete}$, then the whole polynomial hierarchy collapses to the second level. As I understand, proving that the polynomial hierarchy does not collapse to a particular level is thought to be harder than proving $\text{P}\ne\text{NP}$. $\endgroup$
    – Mark S
    Commented Dec 3, 2017 at 18:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .