The computational complexity of knot genus and spanning area

Abstract

We show that the problem of deciding whether a polygonal knot in a closed three-dimensional manifold bounds a surface of genus at most $g$ is NP-complete. We also show that the problem of deciding whether a curve in a PL manifold bounds a surface of area less than a given constant $C$ is NP-hard.