Moving between 3-manifold triangulations is NP-hard

Stephan Tillmann, Anastasiia Tsvietkova

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-ha…