3
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

To your questions about upper bounds: turning a diagram into a triangulation can using linearly many tetrahedra, purely locally -- you explicitly construct a gadget to put in at each crossing, containing I think eight tetrahedra. It's not too hard to construct yourself. (Going the other way -- from triangulation to diagram -- is where it can blow up exponentially; torus knots exhibit this.)

There aren't many complete knot invariants, so if you're determining if two knots are isotopic, you're probably either searching Reidemeister moves (in which case, how do you bound that search? we don't currently know) or, as you say, you're deciding homeomorphism of (oriented) knot complements. One way of extending the 3-manifold homeomorphism algorithm to oriented 3-manifold homeomorphism is to extend the algorithm to decide homeomorphism of 3-manifolds with boundary pattern. See Chapter 6 of Matveev's book Algorithmic Topology and Classification of 3-Manifolds for an explanation of this approach, which also allows you to decide link isotopy. (Roughly speaking, for knots, you decorate the boundary with a graph that is not symmetric under an orientation flip.) Although of course it doesn't cover progress since 2005, that is generally a very good book for learning about triangulation-focused approaches to 3-manifold algorithms.

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .