Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
I'd like to add the following question: what is the best known efficiency of such an algorithm (in terms of the number of crossings of the knot diagram, say)? –  gowers Jan 25 '11 at 19:21
    
Re complexity: This doesn't answer your question definitively (maybe others will), but: (a) Unknotting is in NP, and (b) there is an upper bound exponential in the number of crossings. Haas, Lagarias, and Pippenger are responsible for these results. –  Joseph O'Rourke Jan 25 '11 at 20:01
    
@Joseph O'Rourke: do you know of a reference for the fact that unknotting is an NP problem? –  Jim Conant Jan 25 '11 at 20:05
    
@Jim: It looks like Joe already edited his comment to answer your question, but here's a link to the Hass, Lagarias and Pippenger article: portal.acm.org/citation.cfm?id=301970.301971 –  Peter Shor Jan 25 '11 at 20:18
    
Thanks, Peter (but no one can edit comments--Alas!). Here is the arXiv pre-publication version, which might be more accessible: arxiv.org/abs/math/9807016 . –  Joseph O'Rourke Jan 25 '11 at 20:24
show 1 more comment

3 Answers

up vote 21 down vote accepted

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

share|improve this answer
2  
And thanks for finally logging into MO, Ben. :) –  Ryan Budney Jan 27 '11 at 0:00
1  
Very nice. I'd be interested in seeing the code, especially if the "big red button" is installed, but even without. –  Bill Thurston Jan 27 '11 at 1:52
1  
The source code is all online at regina.sourceforge.net (though warning: there's a lot of it). For a human-readable overview, arXiv:0808.4050 and arXiv:0901.2629 describe the normal surface / vertex enumeration code, which is the computational bottleneck for Haken's algorithm. To run the full procedure: start with a triangulated knot complement (imports from SnapPea are ok), simplify the triangulation to give only two boundary faces, enumerate all vertex normal surfaces, filter out discs using Euler char., then check boundary edge weights to see if any have non-trivial boundary. –  Ben Burton Jan 27 '11 at 2:19
    
BTW, as of Regina release 4.93 the "big red button" is there. Load a 3-manifold triangulation then button under Recognition -> Solid torus. –  Ryan Budney Jul 23 '12 at 19:15
add comment

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.

share|improve this answer
add comment

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: http://front.math.ucdavis.edu/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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.