Wolfgang Haken found an algorithm to tell if a knot is trivial, and, more generally with Hemion, if two knots are equivalent.

Joel Hass, Jeff Lagarias and Nick Pippinger proved in 1999 that telling that a knot is unknotted is in **NP**. This is a major result!

An outstanding problem for many years was to determine if telling that a knot is unknotted is in** coNP** or equivalently if telling that a knot is nontrivial is in NP as well. A few month ago Greg Kuperberg proved it under **GRH **(the generalized Riemann hypothesis)! Amazing! Kuperberg ingenious short proof is based on a recent important knot-theoretic result by Kronheimer and Mrowka combined with computational complexity result by Koiran (discussed in the section “from Primes to Complexity”over this GLL’s post).

There were several results in knot theory in recent years that gradually showed that several invariants (related, generally speaking, to Jones polynomials but more detailed, e.g., Khovanov homology,) are enough to tell if a knot is trivial. I am not so sure about how this fascinating story goes.

An earlier, different, approach (via the Thurston norm) from 2002 to showing that verifying that a knot is trivial is in coNP was by Ian Agol. ** **

It is very interesting if the dependence on GRH can be removed. Of course, a major problem is if telling if a knot is trivial is in P. Showing that the problem is in BQP will also be great.

Eralier, in a SODA 2005 article, Hara, Tani, and Yamamoto proved that unknotting is in **AM** ** coAM.** As mentioned in the comments the argument was incomplete. (One thing I learned from Greg’s preprint is that there is a preprint by Chad Musick who is describing a polynomial-time algorithm for testing if a knot is trivial. His work is based on a knot-invariant called “the crumble,” and its status is unclear at present.)

I am not sure what is the complexity for telling if two knots are equivalent. Haken and Hemion proved that it is decidable. Telling if a knot is trivial feels a little like PRIMALITY while telling two knots apart feels a little like FACTORING. Here is a survey article by Joel Hass on the computability and complexity of knots and 3-manifolds equivalence. It looks that the algorithmic theory of knots is related to both coltures of 3-dim topology, the one related to structural results, combinatorial group theory, geometrization etc, and the other related to invariants and physics, and this is nice. See also the post over GLL entitled “What makes a knot knotty.”

And here is Greg’s description of his ingenious proof. (It is not as easy as the description suggests.) Reading Greg’s short page paper is recommended.

Lior SilbermanSince the difficult point of the article is the

existenceof the certificates, the article omits to explain why they actually certify knottedness — which is because the complement of the trivial knot has a commutative fundamental group.jeffgericksonThere is a subtle flaw in the Hara-Tani-Yamamoto proof, which I heard about from Tasos Sidiropoulos. The authors have since retracted their claims.

Greg KuperbergHi Gil. Thanks a lot for the plug! Just a few comments: As Jeff Erickson says, and my paper says, the Hara-Tani-Yamamato argument doesn’t work. I personally do not think that they came very close to their AM ∩ coAM claim. As I read their paper, they seem to borrow the proof that

graph non-isomorphism is in NP, and they do not explain why their argument wouldn’t work to distinguish triangulated n-manifolds for all n, which is impossible. Also the paper by Musick is considered inadequate: Alex Coward, who is a postdoc at Davis, says that I can cite him to say that this paper is wrong.

On the other hand, Ian Agol, who has done other spectacular things lately, told he me that he still thinks that he can prove that knottedness is in NP unconditionally. His approach uses normal surface theory, like the certificate for unknottedness but more complicated. However he did not yet write the paper.

Also it should be Koiran and not Korian.

GK: thanks, Greg. (I edited the post.)dmoskovichOn Feb 27 2013, the preprint in question by Chad Musick was withdrawn from ArXiv, with the comment:

Gil KalaiPost authorThanks, Daniel, for the information.

Chad MusickHi everyone,

The last I heard, Coward’s objection to my paper was based on a paper by Alexander Zupan (“Unexpected local minima in the width complexes for knots”). On April 28, I posted a revision of my paper that avoids this issue by using a slightly different type of move than the original version. Specifically, moves take place in a punctured sphere, rather than in a punctured plane, and this form allows Zupan’s Figure 1 to be easily simplified.

Gil KalaiDear Chad, thanks for sharing it with us and best luck with your project.

Pingback: Some Updates | Combinatorics and more