Knottedness is in NP, modulo GRH

Abstract

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.

7 pages; minor update

Cited by in corpus (6)

• Integer homology 3-spheres admit irreducible representations in SL(2,C)
• Decision problems, complexity, traces, and representations
• Embeddability in the 3-sphere is decidable
• The complexity of detecting taut angle structures on triangulations
• On the Complexity of Immersed Normal Surfaces
• On the complexity of torus knot recognition