The homeomorphism problem for 3-manifolds is elementary recursive (Greg Kuperberg, UC Davis)
04.04.2019 14:15
One of the important new topics in geometric topology is the computational complexity of topological questions. In cases when some algorithm is known to answer a topological question, you can still ask whether there is an efficient algorithm. A pivotal, early such result is the theorem of Hass et al that recognizing the unknot is in NP, which makes that problem efficient with artificial help. I will talk about a generalization of this problem, namely, whether two triangulated 3-manifolds are homeomorphic to each other. Thurston recognized that the geometrization implies that the homeomorphism problem is recursive, i.e., that it has an algorithm. While writing a proof of this folklore result, I improved it to show that it is elementary recursive, meaning that work is bounded by a bounded tower of exponentials.
Lieu
Room 17, Séminaire "Topologie et Géométrie"
Organisé par
Section de mathématiquesIntervenant-e-s
Greg Kuperberg, UC Davisentrée libre
Classement
Catégorie: Séminaire