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