Greg Kuperberg: It is in NP to Tell if a Knot is Knotted! (under GRH!)

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 \cap 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.

A Videotape lecture by Greg


This entry was posted in Computer Science and Optimization, Geometry and tagged . Bookmark the permalink.

10 Responses to Greg Kuperberg: It is in NP to Tell if a Knot is Knotted! (under GRH!)

  1. Since the difficult point of the article is the existence of 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.

  2. jeffgerickson says:

    There is a subtle flaw in the Hara-Tani-Yamamoto proof, which I heard about from Tasos Sidiropoulos. The authors have since retracted their claims.

  3. Hi 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.)

  4. Chad Musick says:

    Hi 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.

  5. Pingback: Some Updates | Combinatorics and more

  6. Gil Kalai says:

    The 2013 paper “A polynomial upper bound on Reidemeister moves”
    by Marc Lackenby gives a polynomial upper bound for the number of Reidemeister moves needed
    to unknot an unknot.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s