  We show that the problem of deciding whether a knot in a fixed closed
orientable 3-dimensional manifold bounds a surface of genus at most $g$ is in
co-NP. This answers a question of Agol, Hass, and Thurston in 2002. Previously,
this was known for rational homology 3-spheres, by the work of the first
author.
