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.
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 |