Unknotting problem

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.

[1] In 2011, Greg Kuperberg proved that (assuming the generalized Riemann hypothesis) the unknotting problem is in co-NP,[2] and in 2016, Marc Lackenby provided an unconditional proof of co-NP membership.

[3] In 2021, Lackenby announced an unknot recognition algorithm which he claimed ran in quasi-polynomial time.

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

[5] 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.