Moving between 3-manifold triangulations is NP-hard
arXiv:2606.14413
Abstract
We show that \textsc{number of bistellar moves and sparse degree-two edge collapses for 3-sphere} is NP-hard. It follows that a similar problem for an arbitrary 3-manifold is NP-hard as well. This is the first NP-hardness result concerning moves between two triangulations of a 3-manifold.
13 pages, 7 figures