In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, the
unknotting problem is the problem of algorithmically recognizing the
unknotThe unknot arises in the mathematical theory of knots. Intuitively, the unknot is a closed loop of rope without a knot in it. A knot theorist would describe the unknot as an image of any embedding that can be deformed, i.e. ambient-isotoped, to the standard unknot, i.e. the embedding of the...
, 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 timeIn computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm....
algorithm, that is, whether the problem lies in the complexity class
PIn computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes...
.
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
NPIn computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time"....
, and also in the intersection AM coAM.
In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, the
unknotting problem is the problem of algorithmically recognizing the
unknotThe unknot arises in the mathematical theory of knots. Intuitively, the unknot is a closed loop of rope without a knot in it. A knot theorist would describe the unknot as an image of any embedding that can be deformed, i.e. ambient-isotoped, to the standard unknot, i.e. the embedding of the...
, 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 timeIn computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm....
algorithm, that is, whether the problem lies in the complexity class
PIn computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes...
.
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
NPIn computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time"....
, and also in the intersection AM coAM. Ian Agol has claimed a proof that unknotting is in
NPIn computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time"....
co-NPIn computational complexity theory, co-NP is a complexity class. A problem is a member of co-NP if and only if its complement is in complexity class NP...
. Since AM is a generalization of
NPIn computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time"....
, the abovementioned
complexity classes are related by the following sequence of set inclusions:
.
Unknotting algorithms
Some known algorithms solving the unknotting problem include:
- Haken
Wolfgang Haken is a mathematician who specializes in topology, in particular 3-manifolds.In 1976 together with colleague Kenneth Appel at the University of Illinois at Urbana-Champaign, Haken solved one of the most famous problems in mathematics, the four-color theorem...
's algorithm - uses the theory of normal surfaceIn mathematics, a normal surface is a surface inside a triangulated 3-manifold that intersects each tetrahedron so that each component of intersection is a triangle or a quad . A triangle cuts off a vertex of the tetrahedron while a quad separates pairs of vertices...
s to check for a normal disc bound by the knot
- An upper bound (exponential in crossing number) exists on the number of Reidemeister move
In the mathematical area of knot theory, a Reidemeister move refers to one of three local moves on a link diagram. In 1926, Kurt Reidemeister and independently, in 1927, J.W. Alexander and G.B...
s needed to change an unknot diagram to the standard unknot diagram. This lends itself for a (very slow) brute-force search algorithm.
- Birman
Joan Birman is an American mathematician, specializing in braid theory and knot theory. Her book Braids, Links, and Mapping Class Groups has become a standard introduction, with many of today's researchers having learned the subject through it...
-Hirsch algorithm - uses braid foliations
- Residual finiteness of the knot group
In mathematics, a knot is an embedding of a circle into 3-dimensional Euclidean space. The knot group of a knot K is defined as the fundamental group of the knot complement of K in R3,...
(which follows from geometrizationThurston's geometrization conjecture states that compact 3-manifolds can be decomposed into submanifolds that have geometric structures. The geometrization conjecture is an analogue for 3-manifolds of the uniformization theorem for surfaces...
of Haken manifoldIn mathematics, a Haken manifold is a compact, P²-irreducible 3-manifold that contains a two-sided incompressible surface. Sometimes one considers only orientable Haken manifolds, in which case a Haken manifold is a compact, orientable, irreducible 3-manifold that contains an orientable,...
s) gives a rather inefficient algorithm: check if the group has a representation into a symmetric groupIn mathematics, the symmetric group on a set is the group consisting of all automorphisms of the set with function composition as the group operation....
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 torusIn mathematics, a solid torus is a topological space homeomorphic to , i.e. the cartesian product of the circle with a two dimensional disc endowed with the product topology. The solid torus is a connected, compact, orientable 3-dimensional manifold with boundary...
.
- 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.
See also
- Algorithmic topology
Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular computational geometry and computational complexity theory....
- Rubinstein–Thompson algorithm for recognizing the 3-sphere
In mathematics, a 3-sphere is a higher-dimensional analogue of a sphere. It consists of the set of points equidistant from a fixed central point in 4-dimensional Euclidean space...