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]
In 2021, Lackenby announced an unknot recognition algorithm which he claimed ran in quasi-polynomial time [4] . As of May 2024, the result has not been published in the peer-reviewed literature.
The unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless. [5]
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, not knot, 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 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 it through itself.
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 and, independently, James Waddell Alexander and Garland Baird Briggs, 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.
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.
In mathematics, Khovanov homology is an oriented link invariant that arises as the cohomology of a cochain complex. It may be regarded as a categorification of the Jones polynomial.
In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements. Research in proof complexity is predominantly concerned with proving proof-length lower and upper bounds in various propositional proof systems. For example, among the major challenges of proof complexity is showing that the Frege system, the usual propositional calculus, does not admit polynomial-size proofs of all tautologies. Here the size of the proof is simply the number of symbols in it, and a proof is said to be of polynomial size if it is polynomial in the size of the tautology it proves.
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.
Knots have been used for basic purposes such as recording information, fastening and tying objects together, for thousands of years. The early significant stimulus in knot theory would arrive later with Sir William Thomson and his vortex theory of the atom.
In computational complexity theory, a problem is NP-complete when:
In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant such that the worst-case running time of the algorithm, on inputs of size , has an upper bound of the form
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 | |
