Kuperberg proves that knottedness is in NP

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