MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
  • 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?)

share|cite|improve this question
1  
"Bar-Natan showed a program to compute the Khovanov homology fast:" What is the reference for this, please? – Sam Nead Feb 27 at 10:49
3  
$O(\sqrt{\text{crossings}})$ does not give time enough to even look at all the crossings. – Mariano Suárez-Alvarez Feb 27 at 16:31
3  
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. – Ryan Budney Feb 27 at 18:48
3  
@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. – Ryan Budney Feb 28 at 6:34
3  
@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 – Ryan Budney Feb 28 at 6:45
up vote 27 down vote accepted

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.

share|cite|improve this answer
1  
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. – Omri Feb 27 at 11:33
1  
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. – David Eppstein Feb 29 at 5:44

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.

share|cite|improve this answer

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.)

share|cite|improve this answer
1  
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 – Neil Hoffman Apr 6 at 0:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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