Unknotting problem

From Wikipedia, the free encyclopedia

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.

Contents 1 Computational complexity 2 Unknotting algorithms 3 See also 4 References

[edit] 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: Today it is known that the unknotting problem is in the complexity class NP, and also in the intersection AM coAM. Ian Agol has claimed a proof that unknotting is in NP co-NP. Since AM is a generalization of NP, the abovementioned complexity classes are related by the following sequence of set inclusions: .

[edit] Unknotting algorithms

Some known algorithms solving the unknotting problem include:

• Haken's algorithm - uses the theory of normal surfaces to check for a normal disc bound by the knot
• An upper bound (exponential in crossing number) exists on the number of Reidemeister moves needed to change an unknot diagram to the standard unknot diagram. This lends itself for a (very slow) brute-force search algorithm.
• Birman-Hirsch algorithm - uses braid foliations
• Residual finiteness of the knot group (which follows from geometrization of Haken manifolds) gives a rather inefficient algorithm: check if the group has a representation into a symmetric group with non-cyclic image while simultaneously attempting to produce a subdivision of the triangulated complement that is equivalent to a subdivision of the triangulated solid torus.
• Knot Floer homology of the knot detects the genus of the knot, which is 0 if and only if the knot is an unknot. A combinatorial version of knot Floer homology allows a straightforward computation.

Understanding the complexity of these algorithms is an active field of study.

[edit] See also

• Algorithmic topology
• Rubinstein–Thompson algorithm for recognizing the 3-sphere

[edit] References

• Masao Hara, Seiichi Tani and Makoto Yamamoto. Unknotting is in . Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
• Ian Agol. Knot genus is NP. Web page with scanned talk slides
• Wolfgang Haken, Theorie der Normalflächen. Acta Math. 105 (1961) 245–375 (Haken's algorithm)
• Joan S. Birman; Michael Hirsch, A new algorithm for recognizing the unknot. Geometry and Topology 2 (1998), 178–220.
• Joel Hass; Jeffrey Lagarias, The number of Reidemeister moves needed for unknotting. J. Amer. Math. Soc. 14 (2001), no. 2, 399–428
• Complexity Zoo provides information about complexity classes and their inclusion relations.