2
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks I read your article a couple of times already. $\endgroup$
    – Niklas Rosencrantz
    Commented Oct 12, 2021 at 12:59
  • $\begingroup$ 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.) $\endgroup$
    – Hermann Gruber
    Commented Oct 12, 2021 at 18:32
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.