Low Dimensional Topology

April 15, 2012

Kuperberg proves that knottedness is in NP

Filed under: 3-manifolds,Combinatorics,Computation and experiment,Misc. — dmoskovich @ 8:40 am

Gil Kalai, my old Graph Theory professor at Hebrew University, and a great mathematical inspiration, who won the Rothschild Prize a few weeks ago (congratulations Gil!), wrote a very nice blog post about another massive recent result in low dimensional topology.

The result is a proof by Greg Kuperberg that to determine that a knot is not an unknot is in NP, assuming the Generalized Riemann Hypothesis (GRH). By a 1999 result of Hass, Lagarias, and Pippinger, to determine that a knot is unknotted is in NP. So we already knew that, if K is unknotted, then there exists an algorithm to prove this by generating a certificate that can be verified in polynomial time, but this algorithm might run forever if K turned out to be knotted. Kuperberg’s result now is that, there exists an algorithm which assumes the GRH and which generates a certificate that K is knotted, that can be verified in polynomial time. This is a really wonderful result!!! It is an encouraging sign that knot identification might be an algorithmically tractable problem- certainly it isn’t NP hard. Moreover, Greg Kuperberg explains in the comments that Ian Agol, who has been quite a bit in the news lately, has ideas to remove the dependence on the GRH, using normal surface theory.

With the VHC looking to have been proven, we now have a nice qualitative working understanding of 3-manifold topology. It would seem to me that the next step, after digesting it, would be to put it to work to build `infrastructure’ in the form of improved manifold censi and software tools for 3-manifold identification. Of course, knot complements fit into this story as a nice sub-class of 3-manifolds. Then, we can think about questions concerning families of 3-manifolds. Questions in which the conjectures are still to be discovered.

A classification of a set of objects does not necessarily end its mathematical interest. After all, since antiquity we have had a classification of natural numbers. (This analogy is in Joel Hass’s survey paper on 3-manifold computability and complexity).

About these ads

3 Comments »

  1. Ian has more than just a claim (but less than a paper!): he has talk slides.:

    Comment by Saul Schleimer — April 15, 2012 @ 1:21 pm | Reply

    • This is cool!!! Thanks!

      Comment by dmoskovich — April 15, 2012 @ 5:38 pm | Reply

  2. Grr – I couldn’t get html to work? Here is the link as text:

    http://homepages.math.uic.edu/~agol/coNP/coNP1.html

    Comment by Saul Schleimer — April 15, 2012 @ 1:23 pm | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 208 other followers

%d bloggers like this: