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

 Department of Mathematics

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.

 events@math.berkeley.edu