Geometry, Topology and Dynamics Seminar
Greg Kuperberg
UC Davis
Knottedness is in NP, modulo GRH
Abstract: In this talk I will discuss my result that confirming that a knot diagram is a non-trivial knot is in the complexity class NP, assuming the Generalized Riemann Hypothesis. Time permitting, I will also discuss related results, in particular the earlier result of Hass, Lagarias, and Pippenger that unknottedness is in NP. Everything will be on the theme of qualitative complexity theory in geometric topology, in other words, what you can compute in polynomial time with help.
Wednesday September 16, 2015 at 3:00 PM in SEO 636