On the complexity of cusped non-hyperbolicity

joint with Neil Hoffman

Posted as arXiv:1907.01675.

In this project we wanted to determine the computational complexity of the decision problem of hyperbolicity among triangulations of three-manifolds. We found that among triangulations of (generalized) nontrivial link exteriors, the problem is in coNP if three-sphere recognition is in coNP (and is unconditionally in coNP for irreducible such link exteriors.) That is, given a triangulation of a nontrivial link exterior that is not hyperbolic, there is a Nice Proof, verifiable in time polynomial in the number of tetrahedra in the triangulation, of the fact that this three-manifold is not hyperbolic, assuming the same is true for the problem of three-sphere recognition.