# Complexity of Unknotting problems

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

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?

## 2 Answers

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

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. .

• 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 – Hermann Gruber Feb 3 at 8:51