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

5more comments