6
$\begingroup$

The complexity of the Unknotting problem is known to be in $\mathrm{NP} \cap\mathrm{co\text-NP}$, see references:

  1. The Computational Complexity of Knot Problems.
  2. Knottedness is in NP, modulo GRH. .
  3. Unknotting is in $\mathrm{AM}\cap\mathrm{co\text-AM} $.

Some even believe the problem to be in $P$, but to relax the ptime constraints, due to (maybe) either the cost, or diagram of the knot. It maybe there exists an Arthur-Merlin type protocol for unknottedness. This could lead to possibly interesting applications too. Also, if Unknottedness is $\mathrm{NP}$ -complete then the polynomial hierarchy collapses.

But by relaxing the ptime constraints to a quasipolynomial one leads one to quasipolynomial time algorithm for Unknotting. Is there any such quasipolynomial time algorithm for Unknotting?

What (if any) would be the implications of such a quasipolynomial algorithm be to other conjectures such as GRH(?), ETH, or even SETH?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
9
$\begingroup$

Such a quasi-polynomial algorithm has just been claimed by Marc Lackenby from Oxford University. He will present in next Tuesday (02 Feb 2021) in a Zoom talk: https://www.math.ucdavis.edu/research/seminars/?talk_id=6082

Improve this answer
$\endgroup$
3
$\begingroup$

The outline from Marc Lackenby's talk about a quasipolynomial algorithm for Unknottedness. Unknot recognition in quasipolynomial time outline.. Under the talks section there are slides about the algorithm.

And for the seminar video, which has been uploaded link to the video and more about the result. .

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ For those who might have difficulties with following arguments involving Heegard splittings and incompressible (incomprehensible?) surfaces... Here is also a short announcement of the talk by the university in layman's terms, with some historical background on the problem: maths.ox.ac.uk/node/38304 $\endgroup$
    – Hermann Gruber
    Feb 3, 2021 at 8:51

Your Answer

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

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