Computational Complexity of Avalanches in the Kadanoff Sandpile Model
Formenti
E
author
Goles
E
author
Martin
B
author
2012
English
This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 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 NC1 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.
Kadanoff Sandpile Model
Bak Sandpile Model
Sandpiles Models
Complexity
Discrete Dynamical Systems
Self-Organized Criticality (SOC)
WOS:000302777200008
exported from refbase (show.php?record=208), last updated on Mon, 28 May 2012 07:20:22 -0400
text
files/208_Formenti_etal2012.pdf
10.3233/FI-2012-643
Formenti_etal2012
Fundamenta Informaticae
Fundam. Inform.
2012
Ios Press
continuing
periodical
academic journal
115
1
107
124
0169-2968