Unknotting problem
From Wikipedia, the free encyclopedia
In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some input, e.g., a knot diagram.
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 
coAM.
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.
[edit] See also
- Algorithmic topology
- Rubinstein-Thompson algorithm for 3-sphere recognition
[edit] References
- Masao Hara, Seiichi Tani and Makoto Yamamoto. Unknotting is in
, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
