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 的复杂性 。 在更广泛的背景下, 我们的结果有助于分析三度的计算模型的内位数分析。

0
下载
关闭预览

相关内容

【AAAI2022】混合图神经网络的少样本学习
专知会员服务
44+阅读 · 2021年12月14日
【论文】结构GANs,Structured GANs,
专知会员服务
14+阅读 · 2020年1月16日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Type-augmented Relation Prediction in Knowledge Graphs
Arxiv
6+阅读 · 2018年11月29日
Arxiv
3+阅读 · 2018年2月20日
VIP会员
相关VIP内容
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员