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
**S**^{3} - *T*_{K} where *T*_{K}
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