Computational complexity of avalanches in the Kadanoff sandpile model

Enrico Formenti, Eric Goles, Bruno Martin

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC 1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC 1 for one-dimensional sandpiles and P-complete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak's model of two-dimensional sandpiles.

Original languageEnglish
Pages (from-to)107-124
Number of pages18
JournalFundamenta Informaticae
Issue number1
StatePublished - 2012
Externally publishedYes


  • Bak Sandpile Model
  • Complexity
  • Discrete Dynamical Systems
  • Kadanoff Sandpile Model
  • Sandpiles Models
  • Self-Organized Criticality (SOC)


Dive into the research topics of 'Computational complexity of avalanches in the Kadanoff sandpile model'. Together they form a unique fingerprint.

Cite this