Duncan Adamson ; Argyrios Deligkas ; Vladimir Gusev ; Igor Potapov - On the Hardness of Energy Minimisation for Crystal Structure Prediction

fi:7374 - Fundamenta Informaticae, February 2, 2022, Volume 184, Issue 3
On the Hardness of Energy Minimisation for Crystal Structure Prediction

Authors: Duncan Adamson ; Argyrios Deligkas ; Vladimir Gusev ; Igor Potapov

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.


Volume: Volume 184, Issue 3
Published on: February 2, 2022
Accepted on: December 27, 2021
Submitted on: April 15, 2021
Keywords: Computer Science - Computational Complexity,68Q25


Share

Consultation statistics

This page has been seen 78 times.
This article's PDF has been downloaded 43 times.