6
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 23, 2010 at 21:57
  • $\begingroup$ @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. $\endgroup$
    – user6976
    Commented Nov 24, 2010 at 15:06
  • $\begingroup$ @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$. $\endgroup$
    – Sam Nead
    Commented Nov 25, 2010 at 17:19

You must log in to answer this question.