Why is it so hard to implement Haken's Algorithm for knot theory?

Question

Why is it so hard to implement Haken's Algorithm for recognizing whether a knot is unknotted? (Is there a computer implementation of this algorithm?)

Answer 1

Regarding Haken's algorithm: It's not so hard to implement (it's essentially implemented in Regina, though at present you need to type a few lines of python to glue the bits together; a single "big red button" is on its way). However, it's hard to run, since the algorithm has exponential running time (and, depending on how you implement it, exponential memory use).

There are two facts that make Haken's algorithm easier to implement than many other normal surface decision algorithms:

• You only need to search through vertex normal surfaces, not fundamental normal surfaces (Jaco & Tollefson, 1995). Vertex normal surfaces are much easier (and much faster) to enumerate.
• The test that you apply to each vertex normal surface is relatively simple (see if it describes a disk with non-trivial boundary). For other problems (notably Hakenness testing), the test that you apply to each vertex normal surface can be far more difficult than the original vertex enumeration.

The reason Haken's algorithm is slow is that vertex enumeration is NP-hard in general. There are some tempting short-cuts: one is to run $3^n$ polynomial-time linear programs that maximise Euler characteristic over the $3^n$ possible combinations of quad types. However, experimental experience suggests that this short-cut makes things worse: solving $3^n$ linear programs guarantees $\Omega(3^n)$ running time even in the best case for a non-trivial knot. On the other hand, if you perform a full vertex enumeration (and you structure your vertex enumeration code well [1]) then you often see much faster running times in practice, even though the theoretical worst case is slower.

An aside (which has already been noted above): there are much faster heuristic tests for unknot recognition, though these are not always guaranteed to give a definitive answer. SnapPea has some, as does Regina. There are many fast ways of proving you have a non-trivial knot (e.g., invariants or geometric structures). One fast way of proving you have a trivial knot is to triangulate the complement and "greedily simplify" this triangulation. If you're lucky, you get an easily-recognised 1-tetrahedron solid torus. If you're unlucky, you go back and run Haken's algorithm. The interesting observation here is that, if your greedy simplification is sophisticated enough, you almost always get lucky. (This is still being written up, but see arXiv:1011.4169 for related experiments with 3-sphere recognition.)

Btw, thanks Ryan for dragging me online. :)

[1] arXiv:0808.4050, arXiv:1010.6200

Answer 2

First, I'd like to remark that there is a computer programs that will tell if a knot is unknotted, namely Jeff Weeks Snappea. It's not rigorously proven to work as is, but in practice it always works.

The main difficulty with Haken's algorithm is the immense size of the objects that must be surveyed. For a 3-manifold described by gluing $n$ simplices together, there are $3^n$ integer programming problems that among them represent every possible incompressible surface in the manifold, each one of dimension linear in $n$ (details depend on exactly how this is implemented). Each of these integer programming problems in itself is challenging: each has a finite semigroup basis for the solution set, but the size of the basis grows exponentially with $n$. The exponent of growth is sufficiently high that it becomes rapidly hopeless. For simple knot diagrams, everything is already known, and there's not much point. If you get up to knot diagrams with perhaps 20 crossing, then there would be perhaps $3^{20} > $3 billion integer programming problems, each involving very many fundamental solutions with perhaps 100-digit integers that are not easy to identify. There may be various shortcuts and simplifications, but improvements only will increase the complexity of manifolds that can be analyzed by a little bit.

In contrast, Snappea can easily handle knot projections with a hundred or two hundred crossings very quickly, orders of magnitude more quickly than the time it takes to draw a picture of the knot.

Answer 3

Ben Burton has implemented Haken's algorithm in Regina. He (and Rubinstein and Tillman) have a functional algorithm to determine if a normal surface in a triangulated 3-manifold is (in)compressible. It's not terribly fast but it's fast enough to give a proof that the Seifert-Weber space does not contain an incompressible surface. This is a recent paper of theirs on the arXiv: https://arxiv.org/abs/0909.4625

The main issue is that Haken's algorithm is extremely memory-intensive. If you run Haken's algorithm on the Rolfsen/Conway table of knots, the first thing you have to do is triangulate the knot complement. Efficient ideal triangulations are readily generated by the algorithm used in SnapPea (originally due to Thurston, as far as I know). But normal surface theory isn't totally happy with ideal triangulations so what Regina does is replace that triangulation with a semi-simplicial triangulation of a compact manifold (the complement of an open tubular neighbourhood of the knot). This makes the triangulation decidedly less efficient. I believe people like Burton, Jaco and Rubinstein are working on avoiding this step but it's not complete.

Anyhow, so you have to subdivide to get to a point where the normal surface theory is happy. Regina can run through the knot tables, applying the Haken algorithm to each knot. On my laptop it completes the knot table in about a day. So it's not terribly slow. But sometimes Regina is using 2 to 4Gb of RAM. And I believe this is largely normal surface enumeration that takes the bulk of the effort. I'll see if I can get Ben to comment.