TY - GEN

T1 - The Complexity of Periodic Energy Minimisation

AU - Adamson, Duncan

AU - Deligkas, Argyrios

AU - Gusev, Vladimir V.

AU - Potapov, Igor

N1 - Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2022/8/1

Y1 - 2022/8/1

N2 - The computational complexity of pairwise energy minimisation of N points in real space is a longstanding 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 Zd 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.

AB - The computational complexity of pairwise energy minimisation of N points in real space is a longstanding 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 Zd 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.

KW - NP-hardness

KW - Optimisation of periodic structures

KW - tiling

KW - undecidability

UR - http://www.scopus.com/inward/record.url?scp=85137560410&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2022.8

DO - 10.4230/LIPIcs.MFCS.2022.8

M3 - Conference contribution

AN - SCOPUS:85137560410

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022

A2 - Szeider, Stefan

A2 - Ganian, Robert

A2 - Silva, Alexandra

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022

Y2 - 22 August 2022 through 26 August 2022

ER -