Adamson, Duncan, Deligkas, Argyrios, Gusev, Vladimir V and Potapov, Igor
(2020)
On the Hardness of Energy Minimisation for Crystal Structure Prediction.
[Internet Publication]
|
Text
1910.12026v1.pdf - Submitted version Download (543kB) | Preview |
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. 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.
| Item Type: | Internet Publication |
|---|---|
| Additional Information: | Short version published in SOFSEM 2020, full version to be published in Fundamenta Informaticae |
| Uncontrolled Keywords: | cs.CC, cs.CC, 68Q25 |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 31 Oct 2019 11:31 |
| Last Modified: | 19 Jan 2023 00:21 |
| DOI: | 10.1007/978-3-030-38919-2_48 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3060099 |
Dimensions
Dimensions
