<p>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: <a href="https://www.math.ucdavis.edu/research/seminars/?talk_id=6082" rel="noreferrer">https://www.math.ucdavis.edu/research/seminars/?talk_id=6082</a></p>

CC BY-SA 4.0
2021-01-29T09:43:39.593Z
2021-01-29T09:43:39.593Z
Denis
<p>The outline from Marc Lackenby's talk about a quasipolynomial algorithm for Unknottedness.
<a href="http://people.maths.ox.ac.uk/lackenby" rel="nofollow noreferrer"> Unknot recognition in quasipolynomial time outline.</a>. Under the talks section there are slides about the algorithm.</p>
<p>And for the seminar video, which has been uploaded link <a href="https://video.ucdavis.edu/media/quasipolynomial-unknot/1_w3i5jvqi" rel="nofollow noreferrer"> to the video and more about the result. </a>.</p>

CC BY-SA 4.0
2021-02-03T08:51:30.417Z
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: https://www.maths.ox.ac.uk/node/38304
Hermann Gruber
CC BY-SA 4.0
2021-02-03T03:09:02.643Z
2021-02-07T19:40:15.417Z
2021-02-07T19:40:15.417Z
user3483902
<p>The complexity of the Unknotting problem is known to be in <span class="math-container">$\mathrm{NP} \cap\mathrm{co\text-NP}$</span>, see references:</p>
<ol>
<li><a href="https://arxiv.org/abs/math/9807016" rel="nofollow noreferrer"> The Computational Complexity of Knot Problems. </a></li>
<li><a href="https://arxiv.org/abs/1112.0845" rel="nofollow noreferrer">Knottedness is in NP, modulo GRH. </a>.</li>
<li><a href="https://dl.acm.org/doi/10.5555/1070432.1070482" rel="nofollow noreferrer" >Unknotting is in <span class="math-container">$\mathrm{AM}\cap\mathrm{co\text-AM} $</span></a>.</li>
</ol>
<p>Some even believe the problem to be in <span class="math-container">$P$</span>, 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 <span class="math-container">$\mathrm{NP}$</span> -complete then the polynomial hierarchy collapses.</p>
<p>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?</p>
<p>What (if any) would be the implications of such a quasipolynomial algorithm be to other conjectures such as GRH(?), ETH, or even SETH?</p>

CC BY-SA 4.0
2021-01-29T10:17:22.800Z
Knottedness is in NP without the need for GRH: https://arxiv.org/abs/1604.00290
Arnaud
<reference-request><cg.comp-geom><topology>
Complexity of Unknotting problems
user3483902
# Complexity of Unknotting problems

(Asked by: username_0 on 2021-01-29)

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.](https://arxiv.org/abs/math/9807016)
2. [Knottedness is in NP, modulo GRH.](https://arxiv.org/abs/1112.0845) .
3. [Unknotting is in $\mathrm{AM}\cap\mathrm{co\text-AM} $](https://dl.acm.org/doi/10.5555/1070432.1070482).

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?

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

> **Comments:**
> **username_1**: Knottedness is in NP without the need for GRH: https://arxiv.org/abs/1604.00290  

---

## 2 answers

### Answer by username_2 on 2021-01-29. Score: 9

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>


---

### Answer by username_0 on 2021-02-03. Score: 3

The outline from Marc Lackenby's talk about a quasipolynomial algorithm for Unknottedness.
 [Unknot recognition in quasipolynomial time outline.](http://people.maths.ox.ac.uk/lackenby). 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.](https://video.ucdavis.edu/media/quasipolynomial-unknot/1_w3i5jvqi) .

> **Comments:**
> **username_3**: 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: https://www.maths.ox.ac.uk/node/38304  

---

