On the Hardness of Energy Minimisation for Crystal Structure Prediction



Adamson, Duncan ORCID: 0000-0003-3343-2435, Deligkas, Argyrios, Gusev, Vladimir V and Potapov, Igor
(2021) On the Hardness of Energy Minimisation for Crystal Structure Prediction. FUNDAMENTA INFORMATICAE, 184 (3). pp. 181-203.

Access the full-text of this item by clicking on the Open Access link.

Abstract

<jats:p>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.</jats:p>

Item Type: Article
Uncontrolled Keywords: Energy Minimisation, Graph theory, Euclidean Graphs, NP-Hard Problems, Crystal Structure Prediction
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 26 May 2022 15:48
Last Modified: 22 Nov 2023 22:42
DOI: 10.3233/FI-2021-2096
Open Access URL: https://arxiv.org/pdf/1910.12026.pdf
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3155543