* 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?)



What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka)
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.


