MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.