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. 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. Agol (2002) claimed that the problem of testing whether a knot has genus at least k (for a given number k) is in NP; this would imply that unknotting is in NP ∩ co-NP, but remains unpublished. Hara, Tani & Yamamoto (2005) claimed the weaker result that unknotting is in AM ∩ co-AM; however, later they retracted this claim. Two preprints released in 2011, by Chad Musick and Greg Kuperberg, claimed respectively that the unknotting problem is in P and that (assuming the generalized Riemann hypothesis) it is in co-NP.
The unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless.
Read more about this topic: Unknotting Problem
Famous quotes containing the word complexity:
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)