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
