Can unknots be recognized in polynomial time?
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.
First steps toward determining the computational complexity were undertaken in proving that the problem is in larger complexity classes, which contain the class P. By using normal surfaces to describe the Seifert surfaces of a given knot, Hass, Lagarias & Pippenger (1999) showed that the unknotting problem is in the complexity class NP. Hara, Tani & Yamamoto (2005) claimed the weaker result that unknotting is in AM ∩ co-AM; however, later they retracted this claim. [1] In 2011, Greg Kuperberg proved that (assuming the generalized Riemann hypothesis) the unknotting problem is in co-NP, [2] and in 2016, Marc Lackenby provided an unconditional proof of co-NP membership. [3]
The unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless. [4]
One of Ochiai's unknots featuring 139 vertices, [5] for example, was originally unknotted by computer in 108 hours in 1997, [6] but this time has been reduced in more recent research to 10 minutes. [7]
Several algorithms solving the unknotting problem are based on Haken's theory of normal surfaces:
Other approaches include:
Understanding the complexity of these algorithms is an active field of study.
In the mathematical theory of knots, the unknot, or trivial knot, is the least knotted of all knots. Intuitively, the unknot is a closed loop of rope without a knot tied into it, unknotted. To a knot theorist, an unknot is any embedded topological circle in the 3-sphere that is ambient isotopic to a geometrically round circle, the standard unknot.
In the mathematical field of topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot be undone, the simplest knot being a ring. In mathematical language, a knot is an embedding of a circle in 3-dimensional Euclidean space, . Two mathematical knots are equivalent if one can be transformed into the other via a deformation of upon itself ; these transformations correspond to manipulations of a knotted string that do not involve cutting it or passing through itself.
In the mathematical field of knot theory, a knot invariant is a quantity defined for each knot which is the same for equivalent knots. The equivalence is often given by ambient isotopy but can be given by homeomorphism. Some invariants are indeed numbers (algebraic), but invariants can range from the simple, such as a yes/no answer, to those as complex as a homology theory. Research on invariants is not only motivated by the basic problem of distinguishing one knot from another but also to understand fundamental properties of knots and their relations to other branches of mathematics. Knot invariants are thus used in knot classification, both in "enumeration" and "duplication removal".
A knot invariant is a quantity defined on the set of all knots, which takes the same value for any two equivalent knots. For example, a knot group is a knot invariant.
Typically a knot invariant is a combinatorial quantity defined on knot diagrams. Thus if two knot diagrams differ with respect to some knot invariant, they must represent different knots. However, as is generally the case with topological invariants, if two knot diagrams share the same values with respect to a [single] knot invariant, then we still cannot conclude that the knots are the same.
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.
In the mathematical field of knot theory, the Jones polynomial is a knot polynomial discovered by Vaughan Jones in 1984. Specifically, it is an invariant of an oriented knot or link which assigns to each oriented knot or link a Laurent polynomial in the variable with integer coefficients.
In the mathematical area of knot theory, a Reidemeister move is any of three local moves on a link diagram. Kurt Reidemeister (1927) and, independently, James Waddell Alexander and Garland Baird Briggs (1926), demonstrated that two knot diagrams belonging to the same knot, up to planar isotopy, can be related by a sequence of the three Reidemeister moves.
In knot theory, a knot or link diagram is alternating if the crossings alternate under, over, under, over, as one travels along each component of the link. A link is alternating if it has an alternating diagram.
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.
In mathematics, a Seifert surface is an orientable surface whose boundary is a given knot or link.
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.
In mathematics, Khovanov homology is an oriented link invariant that arises as the homology of a chain complex. It may be regarded as a categorification of the Jones polynomial.
In knot theory, a virtual knot is a generalization of knots in 3-dimensional Euclidean space, R3, to knots in thickened surfaces modulo an equivalence relation called stabilization/destabilization. Here is required to be closed and oriented. Virtual knots were first introduced by Kauffman (1999).
Mikhail Khovanov is a Russian-American professor of mathematics at Columbia University who works on representation theory, knot theory, and algebraic topology. He is known for introducing Khovanov homology for links, which was one of the first examples of categorification.
In the mathematical area of knot theory, the crossing number of a knot is the smallest number of crossings of any diagram of the knot. It is a knot invariant.
Joel Hass is an American mathematician and a professor of mathematics and at the University of California, Davis. His work focuses on geometric and topological problems in dimension 3.
In theoretical physics, the six-dimensional (2,0)-superconformal field theory is a quantum field theory whose existence is predicted by arguments in string theory. It is still poorly understood because there is no known description of the theory in terms of an action functional. Despite the inherent difficulty in studying this theory, it is considered to be an interesting object for a variety of reasons, both physical and mathematical.
Hernando Burgos Soto is a Canadian writer and mathematician, professor of mathematics at George Brown College. He is the author of several math papers in which he introduced some mathematics concepts and extended to tangles some celebrated results of knot theory about the Khovanov homology and the Jones polynomial. During his career as a mathematician, his interests have included Mathematical Statistics, Knot Theory, Algebraic Topology and more recently Mathematical Finance. He is comfortable writing in English and Spanish. When writing in Spanish, he works in the area of prose fiction writing short stories. Some of his short stories were published at the website Cuentos y Cuentos.
Marc Lackenby is a professor of mathematics at the University of Oxford whose research concerns knot theory, low-dimensional topology, and group theory.
| Hyperbolic |
|
|---|---|
| Satellite | |
| Torus | |
| Invariants | |
| Notation and operations | |
| Other | |
