Computational Complexity of the Avalanche Problem for One Dimensional Decreasing Sandpiles
Enrico Formenti, Kévin Perrot and Éric Rémila
In this paper we prove that the general avalanche problem AP is in NC for all decreasing sandpile models in one dimension. It extends the developments of [5] and requires a careful attention on the general rule set considered, stressing the importance of the decreasing property. This work continues the study of dimension sensitive problems since in higher dimensions the problem is P-complete (for monotone sandpiles).
Keywords: Sandpile models, discrete dynamical systems, computational complexity, dimension sensitive problems.