Which knots on 3-dimensional manifolds bound a surface of genus <= g? Is NP-complete. This is a little confusing because a very similar problem, the uknotting problem, the specific case where g = 0, is not known to be NP-hard — there might be a polynomial time solution — and is in NP intersect coNP.