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ématiques

Intervenant-e-s

Greg Kuperberg, UC Davis

entrée libre

Classement

Catégorie: Séminaire