## 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.