Abstrakt
We prove that for every d >= 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978.
Our reduction also yields that for every d >= 2 and k >= 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d >= 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.
Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.