Recognising elliptic manifolds

Abstract

We show that the problem of deciding whether a closed three-manifold admits an elliptic structure lies in NP. Furthermore, determining the homeomorphism type of an elliptic manifold lies in the complexity class FNP. These are both consequences of the following result. Suppose that $M$ is a lens space which is neither ${\mathbb{RP}}^3$ nor a prism manifold. Suppose that $\mathcal{T}$ is a triangulation of $M$. Then there is a loop, in the one-skeleton of the 86th iterated barycentric subdivision of $\mathcal{T}$, whose simplicial neighbourhood is a Heegaard solid torus for $M$.

36 pages, 4 figures, v3 - changes made to reflect referee comments