This was an update to <a href="http://mathoverflow.net/questions/47015/the-flip-graph-of-triangulations">this</a> question, but I decided to make it a separate question. The definition  of the graph of triangulations can be found in the previous question.  

<b> Question. </b> 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?