2026-07-23T19:18:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16806 2024-03-06T10:58:22Z ddc:004 open_access

The Complexity of Periodic Energy Minimisation Adamson, Duncan Deligkas, Argyrios Gusev, Vladimir V. Potapov, Igor Optimisation of periodic structures tiling undecidability NP-hardness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Duncan Adamson and Argyrios Deligkas and Vladimir V. Gusev and Igor Potapov 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.8 urn:nbn:de:0030-drops-168065 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.8 eng https://creativecommons.org/licenses/by/4.0/legalcode