The Computational Complexity of Sandpiles

Abstract

Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d >= 3, we show that this problem is P-complete, so that explicit simulation of the system is almost certainly necessary. We also show that the problem of determining whether a sandpile state is recurrent is P-complete in d >= 3. In d=1, we give two algorithms for predicting the sandpile on a lattice of size n, both faster than explicit simulation: a serial one that runs in time O(n log n), and a parallel one that runs in time O(log^3 n), i.e. in the class NC^3. The latter is based on a more general problem we call Additive Ranked Generability. This leaves the two-dimensional case as an interesting open problem.

References in corpus (9)

• Algebraic Aspects of Abelian Sandpile Models
• Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness
• Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones
• Quasi-Linear Cellular Automata
• The Computational Complexity of Generating Random Fractals
• The Parallel Complexity of Growth Models
• Parallel Algorithm and Dynamic Exponent for Diffusion-limited Aggregation
• Algebraic Aspects of Abelian Sandpile Models
• The Computational Complexity of the Lorentz Lattice Gas

Cited by in corpus (11)

• The Lattice structure of Chip Firing Games and Related Models
• Computational universality of fungal sandpile automata
• Any shape can ultimately cross information on two-dimensional abelian sandpile models
• Some halting problems for abelian sandpiles are undecidable in dimension three
• Parallel dynamics and computational complexity of the Bak-Sneppen model
• Lattice Gas Prediction is P-complete
• Sampling Chaotic Trajectories Quickly in Parallel
• Abelian logic gates
• Avalanche Structure in the Kadanoff Sand Pile Model
• How hard is it to predict sandpiles on lattices? A survey
• Parallel Sandpiles or Spurious Bidirectional Icepiles?