On the Hardness of Energy Minimisation for Crystal Structure Prediction

• Autorzy: Adamson Duncan , Deligkas Argyrios , Gusev Vladimir , Potapov Igor

Identyfikatory

DOI

10.3233/FI-2021-2096

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Energy Minimisation; Graph theory, Euclidean Graphs; NP-Hard Problems; Crystal Structure Prediction

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 184, nr 3
• Strony: 181--203
• Opis fizyczny: Bibiogr. 24 poz., rys., tab.

Twórcy

autor

Adamson Duncan

• Department of Computer Science University of Liverpool, Liverpool, UK

autor

Deligkas Argyrios

• Department of Computer Science Royal Holloway University of London, London, UK

autor

Gusev Vladimir

• Leverhulme Research Centre for Functional Materials Design University of Liverpool, Liverpool, UK

autor

Potapov Igor

• Department of Computer Science University of Liverpool, Liverpool, UK

Bibliografia

• [1] Adamson D, Deligkas A, Gusev VV, Potapov I. On the Hardness of Energy Minimisation for Crystal Structure Prediction. In: Lecture Notes in Computer Science), volume 12011 LNCS. Springer, 2020 pp. 587-596. arXiv: 1910.12026 [cs.CC].
• [2] Lyakhov AO, Oganov AR, Valle M. How to predict very large and complex crystal structures. Computer Physics Communications, 2010. 181(9):1623-1632. doi:10.1016/j.cpc.2010.06.007.
• [3] Woodley SM, Catlow R. Crystal structure prediction from first principles. Nature materials, 2008. 7(12):937-946. doi:10.1038/nmat2321.
• [4] Antypov D, Deligkas A, Gusev V, Rosseinsky MJ, Spirakis PG, Theofilatos M. Crystal Structure Prediction via Oblivious Local Search. CoRR, 2020. abs/2003.12442.
• [5] Mellot-Draznieks C, Girard S, F´erey G, Sch¨on JC, Cancarevic Z, Jansen M. Computational Design and Prediction of Interesting Not-Yet-Synthesized Structures of Inorganic Materials by Using Building Unit Concepts. Chemistry – A European Journal, 2002. 8(18):4102-4113. doi:10.1002/1521-3765(20020916)8:18¡4102.
• [6] Oganov AR, Glass CW. Crystal structure prediction using ab initio evolutionary techniques: Principles and applications. The Journal of chemical physics, 2006. 124(24). doi:10.1063/1.2210932.
• [7] Wang Y, Lv J, Zhu L, Lu S, Yin K, Li Q, Wang H, Zhang L, ma Y. Materials discovery via CALYPSO methodology. Journal of physics. Condensed matter : an Institute of Physics journal, 2015. 27:203203. doi:10.1088/0953-8984/27/20/203203.
• [8] Oganov AR. Crystal structure prediction: reflections on present status and challenges. Faraday Discuss., 2018. 211:643-660. doi:10.1039/C8FD90033G.
• [9] Barahona F. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 1982. 15(10):3241-3253. doi:10.1088/0305-4470/15/10/028.
• [10] Wille LT, Vennik J. Computational complexity of the ground-state determination of atomic clusters. Journal of Physics A: Mathematical and General, 1985. 18(8):L419-L422. doi:10.1088/0305-4470/18/8/003.
• [11] Krishnamoorthy M, Deo N. Node-Deletion NP-Complete Problems. SIAM Journal on Computing, 1979. 8(4):619-625.
• [12] Yannakakis M. Node-Deletion Problems on Bipartite Graphs. SIAM Journal on Computing, 1981. 10(2):310-327. doi:10.1137/0210022.
• [13] Yannakakis M. Node-and edge-deletion NP-complete problems. In: Conference record of the tenth annual ACM Symposium on Theory or Computing (STOC), ACM. 1978 pp. 253-264.
• [14] Faber F, Lindmaa A, von Lilienfeld OA, Armiento R. Crystal structure representations for machine learning models of formation energies. International Journal of Quantum Chemistry, 2015. 115(16):1094-1101. doi:10.1002/qua.24917.
• [15] Collins C, Dyer M, Pitcher M, Whitehead G, Zanella M, Mandal P, Claridge J, Darling G, Rosseinsky M. Accelerated discovery of two crystal structure types in a complex inorganic phase field. Nature, 2017. 546(7657):280. doi:10.1038/nature22374.
• [16] Cerioli MR, Faria L, Ferreira TO, Protti F. A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 2011. 45(3):331-346.doi:10.1051/ita/2011106.
• [17] Clark BN, Colbourn CJ, Johnson DS. Unit disk graphs. Discrete Mathematics, 1990. 86(1):165-177. doi:10.1016/0012-365X(90)90358-O.
• [18] Altschuler JM, Boix-Adsera E. Hardness results for Multimarginal Optimal Transport problems. 2020. 2012.05398.
• [19] Altschuler JM, Boix-Adser`a E. Hardness results for Multimarginal Optimal Transport problems. Discrete Optimization, 2021. 42:100669. doi:https://doi.org/10.1016/j.disopt.2021.100669.
• [20] Buckingham RA. The classical equation of state of gaseous helium, neon and argon. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1938.
• [21] Pisinger D. Linear time algorithms for knapsack problems with bounded weights. Journal of Algorithms, 1999. 33(1):1-14. doi:10.1006/jagm.1999.1034.
• [22] Axiotis K, Tzamos C. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms, 2018.1802.06440.
• [23] Håstad J. Clique is hard to approximate within n-e. Acta Mathematica, 1999. 182(1):105-142. doi:10.1007/BF02392825.
• [24] Garey M, Johnson D. The Rectilinear Steiner Tree Problem is $NP$-Complete. SIAM Journal on Applied Mathematics, 1977. 32(4):826-834. doi:10.1137/0132071.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)