  Crystal Structure Prediction (csp) is one of the central and most challenging
problems in materials science and computational chemistry. In csp, the goal is
to find a configuration of ions in 3D space that yields the lowest potential
energy. Finding an efficient procedure to solve this complex optimisation
question is a well known open problem. Due to the exponentially large search
space, the problem has been referred in several materials-science papers as
"NP-Hard and very challenging" without a formal proof. This paper fills a gap
in the literature providing the first set of formally proven NP-Hardness
results for a variant of csp with various realistic constraints. In particular,
we focus on the problem of removal: the goal is to find a substructure with
minimal potential energy, by removing a subset of the ions. Our main
contributions are NP-Hardness results for the csp removal problem, new
embeddings of combinatorial graph problems into geometrical settings, and a
more systematic exploration of the energy function to reveal the complexity of
csp. In a wider context, our results contribute to the analysis of
computational problems for weighted graphs embedded into the three-dimensional
Euclidean space.
