![Complex Systems Complex Systems](https://www.complex-systems.com/wp-content/themes/complexsystems/img/ui_logo_small.png)
An NP-complete Problem for the Abelian Sandpile Model
Matthias Schulz
Department for Computer Sciences,
University of Karlsruhe,
Am Fasanengarten 5,
76128 Karlsruhe, Germany
Abstract
A configuration of the Abelian sandpile model is called recurrent if grains of sand can be added to it so that the resulting configuration relaxes to the original one; else it is called transient. Given a transient configuration, a recurrent configuration results after adding enough grains of sand. In the case of a three-dimensional sandpile model, it is shown in this paper that the problem of finding the minimal number of grains that have to be added to a given transient configuration to get a recurrent one, interpreted as the distance of this configuration to the set of recurrent configurations, is NP-complete.
https://doi.org/10.25088/ComplexSystems.17.1.17