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:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)