%0 Journal Article
%T Knottedness is in NP, modulo GRH
%A Greg Kuperberg
%J Computer Science
%D 2011
%I arXiv
%X 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.
%U http://arxiv.org/abs/1112.0845v2