Unknotting problem

In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm, that is, whether the problem lies in the complexity class P.

First steps toward determining the computational complexity were undertaken in proving that the problem is in larger complexity classes, which contain the class P. By using normal surfaces to describe the Seifert surfaces of a given knot, Hass, Lagarias & Pippenger (1999) showed that the unknotting problem is in the complexity class NP. Hara, Tani & Yamamoto (2005) claimed the weaker result that unknotting is in ; however, later they retracted this claim. In 2011, Greg Kuperberg proved that (assuming the generalized Riemann hypothesis) the unknotting problem is in co-NP, and in 2016, Marc Lackenby provided an unconditional proof of co-NP membership.

The unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless.

The Ochiai unknot featuring 139 vertices, for example, was originally unknotted by computer in 108 hours, but this time has been reduced in more recent research to 10 minutes.

Several algorithms solving the unknotting problem are based on Haken's theory of normal surfaces:

...
Wikipedia