The computational complexity of knot genus and spanning area

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...