Knottedness is in NP, modulo GRH

Details Knottedness is in NP, modulo GRH Knottedness is in NP, modulo GRH

2011-12-05

arxiv.org/abs/1112.0845v1

Mathematics

Geometric Topology

6 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Knottedness is in NP, modulo GRH does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Knottedness is in NP, modulo GRH, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Knottedness is in NP, modulo GRH will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393422