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.