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.

Computational complexity

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, showed that the unknotting problem is in the complexity class NP. claimed the weaker result that unknotting is in AM ∩ co-AM; however, later they retracted this claim. In 2011, Greg Kuperberg proved that 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.
One of Ochiai's unknots 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.

Unknotting algorithms

Several algorithms solving the unknotting problem are based on Haken's theory of normal surfaces:
Other approaches include:
Understanding the complexity of these algorithms is an active field of study.