# 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?

-

## 1 Answer

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.

I believe that the result is a very simple but very slow (doubly exponential) algorithm to recognize the three-sphere. The proofs, at the very end of the day, rely on normal surface theory and the Rubinstein/Thompson algorithm.

-
The double-exponential algorithm you refer to is presumably for finding a sequence of Pachner moves to a standard triangulation. 3-sphere recognition (no Pachner moves, just Rubinstein's alg) is single-exponential run-time. – Ryan Budney Nov 23 '10 at 21:57
@Ryan and @Sam: I thought that Sergei Ivanov (from Illinois) proved that recognizing sphere is in NP. Anyway, the problem which I am looking for is about the (a) graph of triangulations and the length (existence) of a path between two triangulations on that graph. – Mark Sapir Nov 24 '10 at 15:06
@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