  Given a tame knot K presented in the form of a knot diagram, we show that the
problem of determining whether K is knotted is in the complexity class NP,
assuming the generalized Riemann hypothesis (GRH). In other words, there exists
a polynomial-length certificate that can be verified in polynomial time to
prove that K is non-trivial. GRH is not needed to believe the certificate, but
only to find a short certificate. This result complements the result of Hass,
Lagarias, and Pippenger that unknottedness is in NP. Our proof is a corollary
of major results of others in algebraic geometry and geometric topology.
