The following letter to the editors, which corrects a misstatement in the text, is published in American Scientist Vol. 86, No. 1, page 5, January-February 1998:

Severing Knots

To the Editors:
The column by Brian Hayes on "Square Knots" (Computing Science, November-December) states that: "The fundamental problem of knot theory ... is determining whether two knots are equivalent.... After a century of study this problem remains unsolved." In fact a decision procedure does exist for knot equivalence. The existence of this decision procedure is not known as widely as it could be, and it is not referred to in most textbooks on knot theory. One reason for this may be that it appears to be impractical for actual use on even the simplest knots.

The decision procedure for knot equivalence uses three-manifold topology and studies the knot complement manifold S3 - TK where TK is a solid torus enclosing the knot K as its core. It is based on an approach outlined by Wolfgang Haken in 1962, in work done subsequent to his work on the unknotting problem. The final element in this approach was completed by Geoffrey Hemion in 1979. The resulting decision procedure is described in section 4 of Friedhelm Waldhausen's 1978 article, "Recent results on sufficiently large 3-manifolds" (Proceedings of Symposia in Pure Mathematics 32(2):21-38), where the result is explicitly stated in a corollary on page 35. A detailed exposition (with some omissions) appears in a 1992 book by Hemion, The Classification of Knots and 3-Dimensional Spaces (Oxford University Press). This algorithm is extremely complicated--Hemion's entire book is devoted to its description. There is no explicit bound known for its running time as a function of the total number of crossings in the two knot diagrams whose equivalence is to be decided.

Many of the recent books on knot theory study knot invariants discovered since the work of Vaughn Jones in 1985. There is currently no decision procedure known for knot equivalence that is based on using knot polynomial invariants such as the Jones polynomial, HOMFLY polynomial or Vassiliev invariants. A discussion of some of these issues can be found in D. J. A. Welsh, Complexity: Knots, Colourings and Counting (Cambridge University Press, 1993).

Joel Hass
University of California
Davis, CA

Jeffrey C. Lagarias
AT&T Laboratories
Florham Park, NJ

Nicholas Pippenger
University of British Columbia
Vancouver