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:
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).
University of California
Jeffrey C. Lagarias
Florham Park, NJ
University of British Columbia