Detecting the unknot in polynomial time

Charles Delman and Keith Wolcott


Historically, researchers have tried to detect if a diagram is unknotted by searching for moves which would reduce the complexity of the diagram. As is well known, this approach has a bad history! To avoid it, we immediately construct the Seifert surface, $S_1$, for the knot diagram and thicken it to a handlebody. We then choose, in a fairly canonical way, a complete disk system for the handlebody complementary to the thickened $S_1$ and cut along these disks. The knot is now represented by the edges of a graph on the surface of the resulting ball. It is the complexity of this graph, along with the genus of the surface on which the knot lies, which will be reduced.

The algorithm performs efficiently calculatable moves on the graph to find compressions of successive spanning surfaces for $K$ until either an incompressible surface or a disk is obtained. We currently estimate its complexity to be no greater than $O(n^3)$, where $n$ is the number of crossings.

At the time of this writing, this work is in progress. The validity of the algorithm rests on a conjecture about the effects of adding handles to a standardly embedded handlebody in $S^3$.


Back to Special Session on Topology of 3-manifolds