How hard is it to predict sandpiles on lattices? A survey

DOI10.3233/FI-2020-1879zbMATH Open1445.37006arXiv1909.12150MaRDI QIDQ5114215FDOQ5114215

Authors: Kévin Perrot, Enrico Formenti 

Publication date: 21 June 2020

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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 $c$ and a cell $x$ in $c$, if cell $x$ 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?

Full work available at URL: https://arxiv.org/abs/1909.12150

Recommendations

• On the complexity of sandpile prediction problems
• The computational complexity of sandpiles
• The computational complexity of one-dimensional sandpiles
• New Computational Paradigms
• Computational complexity of avalanches in the Kadanoff sandpile model

zbMATH Keywords

sandpile modelsprediction problembehavioral complexity

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Dynamical aspects of statistical mechanics (37A60) Simulation of dynamical systems (37M05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (15)

• Computing with sand: on the complexity of recognizing two-dimensional sandpile critical configurations
• Embedding arbitrary Boolean circuits into fungal automata
• On the complexity of sandpile critical avalanches
• On the predictability of the abelian sandpile model
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• Predictability and scaling in a BTW sandpile on a self-similar lattice
• The computational complexity of one-dimensional sandpiles
• New Computational Paradigms
• Embedding arbitrary Boolean circuits into fungal automata
• On the complexity of sandpile prediction problems
• HOW SIZE OF TARGET AVALANCHES INFLUENCES PREDICTION EFFICIENCY
• Some halting problems for abelian sandpiles are undecidable in dimension three
• Computational complexity of the avalanche problem for one dimensional decreasing sandpiles
• Sandpile toppling on Penrose tilings: identity and isotropic dynamics
• Sandpile prediction on a tree in near linear time

This page was built for publication: How hard is it to predict sandpiles on lattices? A survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114215)