3-Manifold Seminar: Algorithms in 3-Manifold Theory
Seminar | November 7 | 11:10 a.m.-12:30 p.m. | 939 Evans Hall
James Dix, UC BERKELEY
Following a survey paper of Lackenby, we explore the complexity classes of various problems in 3-manifold theory. Examples include unknot detection being in NP and co-NP, link genus being NP-hard, and the homeomorphism problem being computable. We reference conjectures in computer science about various complexity classes to suggest which questions may have more efficient algorithms and which ones do not.