Technical Reports

The ICICS/CS Reading Room

UBC CS TR-98-07 Summary

The Computational Complexity of Knot and Link Problems, May 28, 1998 Joel Hass, Jeffrey C. Lagarias and Nicholas Pippenger, 32 pages

The Computational Complexity of Knot and Link Problems Joel Hass Department of Mathematics University of California, Davis Davis, CA 95616 USA Jeffrey C. Lagarias Information Sciences Research A T & T Labs 180 Park Avenue Florham Park NJ 07932-0971 USA Nicholas Pippenger Department of Computer Science University of British Columbia Vancouver, BC V6T 1Z4 CANADA We consider the problem of deciding whether a polygonal knot in three dimensional space, or alternatively a knot diagram, is unknotted (that is, whether it is capable of being deformed continuously without self-intersection so that it lies in a plane.) We show that the problem, UNKNOTTING PROBLEM, is in NP. We also consider the problem, SPLITTING PROBLEM, of determining whether two or more such polygons can be split (that is, whether they are capable of being continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it) and show that it is also in NP. We show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE. We also give exponential worst-case running time bounds for deterministic algorithms to solve each of these problems. These algorithms are based on the use of normal surfaces and decision procedures due to W. Haken, with recent extensions by W. Jaco and J. F. Tollefson.

If you have any questions or comments regarding this page please send mail to