How hard is it to predict sandpiles on lattices? A survey
arXiv:1909.12150
Abstract
Since their introduction in the 80s, sandpile models have raised interest for their simple definition and their surprising dynamical properties. In this survey we focus on the computational complexity of the prediction problem, namely, the complexity of knowing, given a finite configuration and a cell in , if cell will eventually become unstable. This is an attempt to formalize the intuitive notion of "behavioral complexity" that one easily observes in simulations. However, despite many efforts and nice results, the original question remains open: how hard is it to predict the two-dimensional sandpile model of Bak, Tang and Wiesenfeld?
arXiv commentto appear in Fundamenta Informaticae
References in corpus (5)
- The Computational Complexity of Sandpiles
- Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness
- The Computational Complexity of the Lorentz Lattice Gas
- Some halting problems for abelian sandpiles are undecidable in dimension three
- Any shape can ultimately cross information on two-dimensional abelian sandpile models