We show that the problem of determining whether a knot bounds a surface of genus <=g in a 3-manifold is NP-complete.