<p>To complete the first answer, the equivalence problem is decidable (this dates back to haken, a good reference is Lackenby's survey Elementary Knot Theory ). It is neither known to be in NP nor known to be NP-hard.</p>
<p>The crossing number of a knot/link is not known to be in NP (even if you give me the diagram with the fewest crossings I would need to solve the equivalence problem to recognize my knot). We proved that it is NP-hard for links: <a href="https://www.worldscientific.com/doi/abs/10.1142/S0218216520500431" rel="nofollow noreferrer">https://www.worldscientific.com/doi/abs/10.1142/S0218216520500431</a> For knots this is open.</p>

CC BY-SA 4.0
2021-10-12T12:59:44.290Z
Thanks I read your article a couple of times already.
Niklas Rosencrantz
CC BY-SA 4.0
2021-10-12T18:32:50.980Z
Thanks for the update! I didn't know about this one. (My very first research result had been about the crossing number of links. Back in 2003. Oh well.)
Hermann Gruber
CC BY-SA 4.0
2021-10-12T12:46:32.213Z
2021-10-12T12:46:32.213Z
Arnaud
<p>Regarding the HOMPFLY-PT polynomial, evaluating the coefficients of the Jones polynomial is #P-hard, and this of course transfers to the more general HOMPFLY-PT polynomial: <a href="https://doi.org/10.1017/S0305004100068936" rel="nofollow noreferrer">https://doi.org/10.1017/S0305004100068936</a>
On the positive side, this problem is fixed-parameter tractable:
<a href="https://arxiv.org/abs/1712.05776" rel="nofollow noreferrer">https://arxiv.org/abs/1712.05776</a></p>
<p>Regarding the unknotting problem, Marc Lackenby recently announced a quasipolynomial time algorithm:
<a href="https://www.maths.ox.ac.uk/node/38304" rel="nofollow noreferrer">https://www.maths.ox.ac.uk/node/38304</a>
That problem is known to be both in NP and in coNP, as summarized in the wikipedia article: <a href="https://en.m.wikipedia.org/wiki/Unknotting_problem#Computational_complexity" rel="nofollow noreferrer">https://en.m.wikipedia.org/wiki/Unknotting_problem#Computational_complexity</a>
The results indicate that this problem is very unlikely to be NP-complete.</p>
<p>I'm not sure about the link equivalence problem and the crossing number problem.</p>

CC BY-SA 4.0
2021-10-10T21:55:00.740Z
2021-10-10T22:00:15.430Z
2021-10-10T22:00:15.430Z
Hermann Gruber
<p>I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-complete:</p>
<ul>
<li>The equivalence problem for links (and knots) as described in knot theory.</li>
<li>The unknot recognition problem i.e. to determine if an arbitrary knot is trivial (the empty knot).</li>
<li>Computing the link crossing number for an arbitrary link (or knot).</li>
</ul>
<p>But it is known that the above problems are decidable and some (all?) of them are NP-hard. I thought I read something that the computation of the homfly polynomial is NP complete via a reduction to colouring of graphs, but can we confirm that it is the case?</p>

<reference-request><np-hardness><cg.comp-geom><topology>
Status of certain problems in knot theory
Niklas Rosencrantz
# Status of certain problems in knot theory

(Asked by: username_0 on 2021-09-26)

I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-complete:

* The equivalence problem for links (and knots) as described in knot theory.
* The unknot recognition problem i.e. to determine if an arbitrary knot is trivial (the empty knot).
* Computing the link crossing number for an arbitrary link (or knot).

But it is known that the above problems are decidable and some (all?) of them are NP-hard. I thought I read something that the computation of the homfly polynomial is NP complete via a reduction to colouring of graphs, but can we confirm that it is the case?

**Tags:** reference-request, np-hardness, cg.comp-geom, topology


---

## 2 answers

### Answer by username_1 on 2021-10-12. Score: 4 | Accepted answer

To complete the first answer, the equivalence problem is decidable (this dates back to haken, a good reference is Lackenby's survey Elementary Knot Theory ). It is neither known to be in NP nor known to be NP-hard.

The crossing number of a knot/link is not known to be in NP (even if you give me the diagram with the fewest crossings I would need to solve the equivalence problem to recognize my knot). We proved that it is NP-hard for links: <https://www.worldscientific.com/doi/abs/10.1142/S0218216520500431> For knots this is open.

> **Comments:**
> **username_0**: Thanks I read your article a couple of times already.  
> **username_2**: Thanks for the update! I didn't know about this one. (My very first research result had been about the crossing number of links. Back in 2003. Oh well.)  

---

### Answer by username_2 on 2021-10-10. Score: 4

Regarding the HOMPFLY-PT polynomial, evaluating the coefficients of the Jones polynomial is #P-hard, and this of course transfers to the more general HOMPFLY-PT polynomial: <https://doi.org/10.1017/S0305004100068936>
On the positive side, this problem is fixed-parameter tractable:
<https://arxiv.org/abs/1712.05776>

Regarding the unknotting problem, Marc Lackenby recently announced a quasipolynomial time algorithm:
<https://www.maths.ox.ac.uk/node/38304>
That problem is known to be both in NP and in coNP, as summarized in the wikipedia article: <https://en.m.wikipedia.org/wiki/Unknotting_problem#Computational_complexity>
The results indicate that this problem is very unlikely to be NP-complete.

I'm not sure about the link equivalence problem and the crossing number problem.


---

