Document Open Access Logo

The Complexity of Periodic Energy Minimisation

Authors Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.8.pdf
  • Filesize: 2.18 MB
  • 15 pages

Document Identifiers

Author Details

Duncan Adamson
  • ICE-TCS, Department of Computer Science, Reykjavik University, Iceland
Argyrios Deligkas
  • Department of Computer Science, Royal Holloway, University of London, UK
Vladimir V. Gusev
  • Materials Innovation Factory, Department of Computer Science, University of Liverpool, UK
Igor Potapov
  • Department of Computer Science, University of Liverpool, UK

Funding

  • Adamson, Duncan: supported by Icelandic Research Fund grant no. 217965.
  • Gusev, Vladimir V.: The author is supported by the Leverhulme Trust via the Leverhulme Research Centre for Functional Materials Design.
  • Potapov, Igor: partially supported by EP/R018472/1.

Cite AsGet BibTex

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov. The Complexity of Periodic Energy Minimisation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.8

Abstract

The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms, even when restricted the integer grid approximation. In this paper we provide a firm answer to the problem on ℤ^d by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing an abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) novel reductions for a large class of generic pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Optimisation of periodic structures
  • tiling
  • undecidability
  • NP-hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Adamatzky. On Diversity of Configurations Generated by Excitable Cellular Automata with Dynamical Excitation Intervals. International Journal of Modern Physics C, 23(12):1250085, November 2012. URL: https://doi.org/10.1142/S0129183112500854.
  2. D. Adamson. Ranking binary unlabelled necklaces in polynomial time. 24th International Conference on Descriptional Complexity of Formal systems (DFCS), Lecture Notes in Computer Science, Springer, 2022. Google Scholar
  3. D. Adamson, A. Deligkas, V. V. Gusev, and I. Potapov. On the hardness of energy minimisation for crystal structure prediction. Fundamenta Informaticae, 184:1-23, February 2022. Google Scholar
  4. Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas. Ranking Bracelets in Polynomial Time. In Paweł Gawrychowski and Tatiana Starikovskaya, editors, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), volume 191 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.CPM.2021.4.
  5. C. Allauzen and B. Durand. Tiling problems. In The Classical Decision Problems, Perspectives in Mathematical Logic, pages 407-420. Springer, 2001. Google Scholar
  6. D. Antypov, A. Deligkas, V.V. Gusev, M. J. Rosseinsky, P. G. Spirakis, and M. Theofilatos. Crystal Structure Prediction via Oblivious Local Search. In SEA 2020, volume 160 of LIPIcs, pages 21:1-21:14, 2020. Google Scholar
  7. R. Berger. The undecidability of the domino problem. Number 66 in memoirs of the american mathematical society. American Mathematical Soc., 1966. Google Scholar
  8. A. Blanca, R. Gheissari, and E. Vigoda. Random-Cluster Dynamics in Z²: Rapid Mixing with General Boundary Conditions. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of LIPIcs, pages 67:1-67:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.67.
  9. S. T. Call, D. Y. Zubarev, and A. I. Boldyrev. Global minimum structure searches via particle swarm optimization. Journal of computational chemistry, 28(7):1177-1186, 2007. Google Scholar
  10. R. Catlow and S. M. Woodley. Crystal structure prediction from first principles. Nature materials, 7(12):937, 2008. Google Scholar
  11. B. A. Cipra. The Ising model is NP-complete. SIAM News, 33(6):1-3, 2000. Google Scholar
  12. C. Collins, M.S. Dyer, M.J. Pitcher, G.F.S. Whitehead, M. Zanella, P. Mandal, J.B. Claridge, G.R. Darling, and M.J. Rosseinsky. Accelerated discovery of two crystal structure types in a complex inorganic phase field. Nature, 546(7657):280, 2017. Google Scholar
  13. V. K de Souza and D. J Wales. The potential energy landscape for crystallisation of a Lennard-Jones fluid. Journal of Statistical Mechanics: Theory and Experiment, 2016(7):074001, July 2016. URL: https://doi.org/10.1088/1742-5468/2016/07/074001.
  14. D. M. Deaven and K. M. Ho. Molecular geometry optimization with a genetic algorithm. Physical review letters, 75(2):288, 1995. Added up to here. Google Scholar
  15. M. S. Dyer, C. Collins, D. Hodgeman, P. A. Chater, A. Demont, S. Romani, R. Sayers, M. F. Thomas, J. B. Claridge, G. R. Darling, and M. J. Rosseinsky. Computationally assisted identification of functional inorganic materials. Science, 340(6134):847-852, 2013. Google Scholar
  16. S. Goedecker. Minima hopping: An efficient search method for the global minimum of the potential energy surface of complex molecular systems. The Journal of chemical physics, 120(21):9911-9917, 2004. Google Scholar
  17. L. A. Goldberg and H. Guo. The Complexity of Approximating complex-valued Ising and Tutte partition functions. Comput. Complex., 26(4):765-833, 2017. URL: https://doi.org/10.1007/s00037-017-0162-2.
  18. L. A. Goldberg and M. Jerrum. Approximating Pairwise Correlations in the Ising Model. ACM Trans. Comput. Theory, 11(4):23:1-23:20, 2019. URL: https://doi.org/10.1145/3337785.
  19. M. Hill, S. Stepney, and F. Wan. Penrose Life: Ash and Oscillators. In Mathieu S. Capcarrère, Alex Alves Freitas, Peter J. Bentley, Colin G. Johnson, and Jon Timmis, editors, Advances in Artificial Life, 8th European Conference, ECAL 2005, Canterbury, UK, September 5-9, 2005, Proceedings, volume 3630 of Lecture Notes in Computer Science, pages 471-480. Springer, 2005. URL: https://doi.org/10.1007/11553090_48.
  20. J. Kari and E. Moutot. Decidability and Periodicity of Low Complexity Tilings. In C. Paul and M. Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 14:1-14:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.14.
  21. H. R. Lewis. Complexity of solvable cases of the decision problem for the predicate calculus. In 19th Annual Symposium on Foundations of Computer Science (FOCS 1978), pages 35-47, 1978. URL: https://doi.org/10.1109/SFCS.1978.9.
  22. D. C. Lonie and E. Zurek. XtalOpt: An open-source evolutionary algorithm for crystal structure prediction. Computer Physics Communications, 182(2):372-387, 2011. Google Scholar
  23. A. O. Lyakhov, A. R. Oganov, and M. Valle. How to predict very large and complex crystal structures. Computer Physics Communications, 181(9):1623-1632, 2010. Google Scholar
  24. J. Maddox. Crystals from first principles. Nature, 335(6187):201-201, 1988. URL: https://doi.org/10.1038/335201a0.
  25. A. R. Oganov and C. W. Glass. Crystal structure prediction using ab initio evolutionary techniques: Principles and applications. The Journal of chemical physics, 124(24), 2006. Google Scholar
  26. J. Pannetier, J. Bassas-Alsina, J. Rodriguez-Carvajal, and V. Caignaert. Prediction of crystal structures from crystal chemistry rules by simulated annealing. Nature, 346(6282):343-345, 1990. Google Scholar
  27. R.J. Pickard, C. J .and Needs. Ab initio random structure searching. Journal of Physics: Condensed Matter, 23(5):053201, 2011. Google Scholar
  28. Z. Rotman and E. Eisenberg. Finite-temperature liquid-quasicrystal transition in a lattice model. Phys. Rev. E, 83:011123, January 2011. URL: https://doi.org/10.1103/PhysRevE.83.011123.
  29. M. U. Schmidt and U. Englert. Prediction of crystal structures. Journal of the Chemical Society, Dalton Transactions, 10:2077-2082, 1996. Google Scholar
  30. J. C. Schön and M. Jansen. First step towards planning of syntheses in solid-state chemistry: determination of promising structure candidates by global optimization. Angewandte Chemie International Edition in English, 35(12):1286-1304, 1996. Google Scholar
  31. H. E. Stanley. Dependence of Critical Properties on Dimensionality of Spins. Phys. Rev. Lett., 20:589-592, March 1968. Google Scholar
  32. D. J. Wales. Exploring Energy Landscapes. Annual Review of Physical Chemistry, 69(1):401-425, 2018. PMID: 29677468. URL: https://doi.org/10.1146/annurev-physchem-050317-021219.
  33. Y. Wang, J. Lv, L. Zhu, S. Lu, K. Yin, Q. Li, H. Wang, L. Zhang, and Y. ma. Materials discovery via CALYPSO methodology. Journal of physics. Condensed matter : an Institute of Physics journal, 27:203203, April 2015. Google Scholar
  34. L. T. Wille and J. Vennik. Computational complexity of the ground-state determination of atomic clusters. Journal of Physics A: Mathematical and General, 18(8):L419-L422, June 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact