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?