What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka) 
*

*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:


*

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

*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?)
 A: 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.
A: 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.
A: 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.)
