Mathematics Colloquium
Neil Hoffman
Oklahoma State
Title: Computational complexity in 3-manifold topology.
Date: Friday, November 1, 2019
Place and Time: Room 101, Love Building, 3:35-4:25 pm
Refreshments: Room 204, Love Building, 3:00 pm
Abstract. A central problem in any field is to recognize the basic objects up to equivalence. In 3-manifold topology, one might ask to identify a 3-manifold up to homeomorphism given a triangulation $\mathcal{T}$. A decision problem asks if we can take a question of the form: "Is $\mathcal{T} \cong S^1 \times D^2$?", follow a finite number of steps and always arrive at a yes or no answer to the question. For that specific problem, Haken showed that such an algorithm exists and in doing so he laid the groundwork for a rich theory, which can be applied more widely to other 3-manifold decision problems. After describing some of the key ideas of this theory, I will describe how more contemporary work of Hass--Lagarias--Pippenger and recent work Lackenby has shed light on the computational complexity of this classical problem. Namely, that it lies in $NP\cap coNP$. In fact, it appears that many 3-manifold problems can lie in this intersection. I will discuss why this is relevant and how it relates to recent work of myself and R. Haraway.