ICS Theory Group

ICS 269, Spring 1997: Theory Seminar


5 December 1997:
The Computational Complexity of Knot and Link Problems
Dan Halem, ICS, UC Irvine

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted (that is, whether it is capable of being continously deformed without self-intersection so that is lies in a plane). We show that this 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 also is in NP. Finally 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.

(From a FOCS '97 paper by Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger.)