Abstract
The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary) as soon as d >= 3. This extends our earlier work with Goaoc, Patakova and Wagner on hardness of shellability of 2-complexes and answers some questions implicitly raised by Danaraj and Klee in 1978 and explicitly mentioned by Santamaria-Galvis and Woodroofe.
Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng andWalkington; and that shellability is NP-hard for 2-complexes embeddable in 3-space, answering another question of Santamaria-Galvis andWoodroofe (in a slightly stronger form than what is given by the main result).