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 $\cap$ 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 $\mathbf{AM} \cap \mathbf{coAM}$ , Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005