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:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)