Celebratio Mathematica — Hass — Complete Bibliography

Complete Bibliography

Works connected to Nicholas John Pippenger

Filter the Bibliography List

year	title	people

			clear

J. Hass, J. C. Lagarias, and N. Pippenger: “The computational complexity of knot and link problems,” pp. 172–181 in Proceedings: 38th annual symposium on the foundations of computer science (Miami Beach, FL, 20–22 October 1997). IEEE Computer Society Press (Los Alamitos, CA), 1997. preliminary report. preliminary report for an article eventually published in J. ACM 46:2 (1999). incollection

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 continuously deformed without self-intersection so that it 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.

J. Hass, J. C. Lagarias, and N. Pippenger: “The computational complexity of knot and link problems,” J. ACM 46 : 2 (March 1999), pp. 185–211. A preliminary report was published in Proceedings: 38th annual symposium on the foundations of computer science (1997). MR 1693203 Zbl 1065.68667 article

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, i.e., capable of being continuously deformed without self-intersection so that it 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, or continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it. We 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. 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. L. Tollefson.