The Complexity of Periodic Energy Minimisation

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
EditorsStefan Szeider, Robert Ganian, Alexandra Silva
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772563
DOIs
Publication statusPublished - 1 Aug 2022
Event47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 - Vienna, Austria
Duration: 22 Aug 202226 Aug 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume241
ISSN (Print)1868-8969

Conference

Conference47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Country/TerritoryAustria
CityVienna
Period22/08/2226/08/22

Keywords

  • NP-hardness
  • Optimisation of periodic structures
  • tiling
  • undecidability

Fingerprint

Dive into the research topics of 'The Complexity of Periodic Energy Minimisation'. Together they form a unique fingerprint.

Cite this