# 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).

## 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

• This is cool!!! Thanks!

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

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

Blog at WordPress.com.