# What is the algorithmic complexity of knot equivalence?

Question. Given two (tame) knots by their link diagrams, what is the algorithmic complexity (e.g. time in the size needed to store the link diagrams) to decide if the represented links are isotopic?

There are several results on related problems in computational knot theory, cf. wikipedia, which imply that knot equivalence is at least NP-hard and BQP-hard.

On the other hand it is known that deciding whether two closed, oriented 3-manifolds given by triangulations are homeomorphic is only known to be elementary recursive (ER), cf. Kuperberg's work.

It is known that equivalence (isotopy) of knots can be reduced to equivalence (homeomorphy) of their knot complement 3-manifolds, which suggests that knot equivalence should also be in ER. There are some obstacles to that which are not clear to me. First given a link diagram for a knot one would have to produce effectively a triangulation of the knot complement and the growth in memory size from link diagram to triangulation has to be controlled compatible with ER. Second the knot complement is oriented but not closed, its boundary being precisely a tubular neighborhood of the knot.

It seems to me reasonable to believe that the growth in size from link diagram to triangulation should be manageable (at most exponential or even polynomial, say) and that Kuperberg's result should be extendable to oriented manifolds with boundary. This answer to a mathoverflow question indeed claims that knot equivalence is in ER.

On the other hand, ER is quite a large class. Given that, e.g., recognizing the trivial knot is in $$\text{NP}\cap\text{co-NP}$$ it seems plausible that the actual complexity of knot equivalence is much lower.

ER consists of problems that admit algorithms of time complexity a tower of exponentials (of order $$k$$) in a polynomial in the input size.

Upper bounds. Are their any results on the size of $$k$$? Are there any algorithms to decide knot equivalence with better complexity and without detouring to equivalence of knot complements known?

Lower bounds. Are there better lower bounds known than NP-hardness or BQP-hardness? E.g. Gröbner bases are EXPSPACE-complete, is it known that such a problem is reducible to knot equivalence?

In terms of results on the size of $$k$$, we can pull this back to giving bounds on the runtime of 3-manifold homeomorphism for manifolds with a single torus boundary component. Scull proved that the problem can be solved for closed hyperbolic manifolds in runtime at most $$2^{2^{t^{O(t)}}}$$, where $$t$$ is the number of tetrahedra in the two triangulations (arXiv:2108.00779).
I don't know of much work on the case with boundary, aside from my own work on Seifert fibered spaces (arXiv:2306.04612) where I prove that the homeomorphism question is in NP, so the runtime is at most $$2^{poly(n)}$$. It wouldn't be hard to make that polynomial explicit. This case covers isotopy between $$K$$ and $$J$$ where $$J$$ is a torus knot. You might also be interested in Haraway-Hoffman's work (arXiv:1907.01675 ) that determining if a manifold (so hence a knot) is not hyperbolic is in NP, assuming $$S^3$$ recognition is in coNP (which is currently known to be true if GRH is true by work of Zentner).
I would guess that the problem should be in NP, so runtime at most $$2^{poly(n)}$$, but that is open. If you fix a link $$L$$, Lackenby has announced that the $$L$$-recognition problem is in NP (see Section 4.4 of "Elementary Knot Theory" in Lectures on Geometry (Clay Lecture Notes), Oxford University Press (2017) but I don't know of a published proof.