Unknotting problem

Unsolved problem in mathematics:

Can unknots be recognized in polynomial time?

Two simple diagrams of the unknot
A tricky unknot diagram by Morwen Thistlethwaite

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, 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 AM ∩ co-AM; however, later they retracted this claim.[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]

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

One of Ochiai's unknots featuring 139 vertices,[5] for example, was originally unknotted by computer in 108 hours,[6] but this time has been reduced in more recent research to 10 minutes.[7]

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.

See also[]

Notes[]

  1. ^ Mentioned as a "personal communication" in reference [15] of Kuperberg (2014).
  2. ^ Kuperberg (2014)
  3. ^ Lackenby (2016)
  4. ^ Kawarabayashi, Kreutzer & Mohar (2010).
  5. ^ Ochiai, M. (1990). "Non-Trivial Projections of the Trivial Knot" (PDF). S.M.F. Asterisque. 192: 7–9.
  6. ^ Grzeszczuk, R.; Huang, M.; Kauffman, L. (1997). "Physically-based stochastic simplification of mathematical knots". IEEE Transactions on Visualization and Computer Graphics. 3 (3): 262–278. doi:10.1109/2945.620492.
  7. ^ Ladd & Kavraki (2004).
  8. ^ Lackenby (2015).
  9. ^ Mijatović (2005).
  10. ^ Burton (2011b).
  11. ^ Dynnikov (2006).
  12. ^ Kronheimer & Mrowka (2011)

References[]

External links[]