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