On the Hardness of Energy Minimisation for Crystal Structure Prediction

15^th January 2020, 14:00
Duncan Adamson
University of Liverpool

Abstract

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 in computational chemistry. Due to the exponentially large search space, the problem has been referred in several materials-science papers as “NP-hard and very challenging” without any formal proof though. 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, this work focuses on the problem of removal: the goal is to find a substructure with minimal potential energy, by removing a subset of the ions from a given initial structure. The 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, the results contribute to the analysis of computational problems for weighted graphs embedded into the three-dimensional Euclidean space, where our new NP-hardness results holds for complete graphs with edges which are proportionally weighted to the distance between the vertices placed in a fixed dimension.

Additional Materials

• https://arxiv.org/abs/1910.12026