Added to Favorites

Popular Searches

Definitions

In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some input, e.g., a knot diagram.## See also

## References

There are several types of unknotting algorithms. A major open problem is to determine if there is such a polynomial time algorithm. The unknotting problem is known to be in NP, and also in AM $cap$ coAM. Ian Agol has claimed a proof that unknotting is in NP $cap$ co-NP.

Some algorithms:

- 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. This gives a 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.

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

- Masao Hara, Seiichi Tani and Makoto Yamamoto. Unknotting is in $mathbf\{AM\}\; cap\; mathbf\{coAM\}$ 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&ndasah;220.
- Joel Hass; Jeffrey Lagarias, The number of Reidemeister moves needed for unknotting. J. Amer. Math. Soc. 14 (2001), no. 2, 399–428

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday August 25, 2008 at 12:49:04 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday August 25, 2008 at 12:49:04 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.