# Poincare conjecture and the graph of triangulations

This was an update to this question, but I decided to make it a separate question. The definition of the graph of triangulations can be found in the previous question.

Question. I was told a few years ago that some computational complexity problem for the triangulation graph (perhaps in dimension 3?) is related to the Poincare conjecture. Unfortunately I forgot what was the problem. Does anybody know?

-

Perhaps you are thinking of the recognition problem for the three-sphere? There are theorems of Aleksandar Mijatovic (Simplifying triangulations of $S^3$) and Simon King (How to make a triangulation of $S^3$ polytopal) that say: If $T$ is a triangulation of $S^3$ with at most $n$ tetrahedra then you need at most $f(n)$ "operations" to transform $T$ into a "standard" triangulation. The function $f$, the operations, and the definition of standard vary between the two papers.
@Ryan - Correct. The point I was making is that the Mijatovic/King algorithm is very simple (brute force search) but slow. @Mark - That is what I am saying. You give me a triangulated manifold, say with $n$ tetrahedra. I produce all triangulations within distance $e^{e^n}$ in the triangulation graph. Then using Mijatovic/King one of those triangulations is the boundary of a four simplex iff the manifold you gave me was $S^3$. – Sam Nead Nov 25 '10 at 17:19