Finding small triangulations of polytope boundaries is hard

We prove that it is NP-hard to decide whether a polyhedral 3-ball can be triangulated with k simplices. The construction also implies that it is difficult to find the minimal triangulation of such a 3-ball. A lifting argument is used to transfer the result also to triangulations of boundaries of 4-polytopes. The proof is constructive and translates a variant of the 3-SAT problem into an instance of a concrete polyhedral 3-ball for which it is difficult to find a minimal triangulation.