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, 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 from a given initial structure. 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.
翻译:晶体结构预测(csp) 是材料科学和计算化学中一个核心和最具挑战性的问题。 在 csp 中, 目标是在3D空间找到一个能产生潜在能量最小的离子配置。 找到一个高效的程序来解决这个复杂的优化问题是计算化学中众所周知的公开问题。 由于搜索空间极大, 这个问题在一些材料科学论文中被称作“ NP- Hard 和非常具有挑战性”, 虽然没有任何正式的证明。 本文填补了文献中的空白, 文献为具有各种现实限制的csp 变量提供了第一批经正式证明的 NP- Hardness 效果。 特别是, 我们侧重于清除问题: 目标是找到一个具有最小潜在能量的子结构, 从一个特定的初始结构中去除一个子项 。 我们的主要贡献是: CPP- Hardness 用于消除 cspot 问题的结果, 将组合图形问题重新嵌入几何环境, 以及更系统地探索能源功能以揭示 cspspin 的复杂性 。 在更广泛的背景下, 我们的结果有助于分析三度的计算模型的内位数分析。