Affiliations: Université Nice–Sophia Antipolis, F-06903 Sophia Antipolis Cedex, France. [email protected] | Universidad Adolfo Ibañez, Av. Diagonal Las Torres 2640, Peñalolen, Santiago, Chile. [email protected] | Université Nice–Sophia Antipolis, F-06903 Sophia Antipolis Cedex, France. [email protected]
Note: [] Work supported by The French National Research Agency project EMC (ANR-09-BLAN-0164). Address for correspondence: Université Nice–Sophia Antipolis, I3S, UMR 6070 CNRS, 2000 route des Lucioles, BP 121, F-06903 Sophia Antipolis Cedex
Note: [] FONDECYT 1100003, BASAL-CMM-U. de Chile, Anillo ACT-88, CNRS.
Note: [] Work supported by The French National Research Agency project EMC (ANR-09-BLAN-0164).
Abstract: 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.
