Computational complexity of avalanches in the Kadanoff sandpile model (Q2883187)

This article deals with the Kadanoff model which generalizes the sandpile model: on a line is arranged a sequence of sand piles, each of which may give one grain to each of its \(p\) right neighbors whenever this ``toppling'' operation does not make it drop lower than its right neighbor (\(p=1\) corresponds to the classical sandpile model; throughout the article, there is a confusion between \(p\) and \(p-1\)).NEWLINENEWLINEThe avalanche problem asks, being given a configuration (a sequence of pile heights, only finitely many of which are nonzero) and an integer position \(k\) (in some interval), whether adding one grain at the leftmost pile and performing successive topplings, some grain will eventually reach pile \(k\).NEWLINENEWLINEIt is proven that this problem is in \(\mathrm{NC}^{1}\) if we require the initial configuration to be nonincreasing (or if \(p=1\)), and conjectured that the general case is P-complete. The model is then generalized to dimension 2, where piles are set on a grid and required to have nonincreasing heights in both every column and every line; one grain is then toppled from a pile to either each of its \(p\) right neighbors or each of its \(p\) top neighbors if this operation preserves the monotonicity conditions. Now, the avalanche problem asks, being given a configuration and a position \((k,l)\) (with some condition on the distance to the origin), whether a sequence of topplings can reach pile \((k,l)\).NEWLINENEWLINEIt is proven that this problem is P-complete if \(p\) is at least 2, by describing logical gates, wires and wire bridges that can form an embedding of Boolean circuits; this allows a reduction from the monotone circuit value problem to the case \(p=2\). It is mentioned that the higher values of \(p\) could be addressed in the same way. The complexity of the avalanche problem gives a rough lower bound for that of predicting the stable limit configuration (known, for \(p=1\), to be in \(\mathrm{NC}^{3}\) in dimension 1 and \(P\)-complete in dimension 3, from [\textit{C. Moore} and \textit{M. Nilsson}, J. Stat. Phys. 96, No. 1--2, 205--224 (1999; Zbl 0964.82037)]). Nevertheless, the complexity of these problems remains open for \(p=1\) in dimension 2, due to the inability of encoding circuit bridges.