The Computational Complexity of Knot and Link Problems

Details The Computational Complexity of Knot and Link Problems The Computational Complexity of Knot and Link Problems

1998-07-03

arxiv.org/abs/math/9807016v1

J. A. C. M. 46 (1999) 185--211.

Mathematics

Geometric Topology

32 pages, 1 figure

Scientific paper

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, {\sc unknotting problem} is in {\bf NP}. We also consider the problem, {\sc unknotting 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 {\bf 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.

Affiliated with

Also associated with

No associations

Rating

The Computational Complexity of Knot and Link Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Computational Complexity of Knot and Link Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Computational Complexity of Knot and Link Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-246166