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

DOI10.3233/FI-2020-1879MaRDI QIDQ5114215zbMATH OpenFDO

Authors Kévin Perrot, Enrico Formenti

Publication date 21 June 2020

Published in Fundamenta Informaticae (Search for Journal in Brave)

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

zbMATH Keywords

behavioral complexityprediction problemsandpile models

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Dynamical aspects of statistical mechanics (37A60) Simulation of dynamical systems (37M05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) 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)

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?

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

Cited in

(17)

• The computational complexity of sandpiles
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• Predictability and scaling in a BTW sandpile on a self-similar lattice
• Sandpile toppling on Penrose tilings: identity and isotropic dynamics
• The computational complexity of one-dimensional sandpiles
• 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
• Sandpile prediction on a tree in near linear time
• Computing with sand: on the complexity of recognizing two-dimensional sandpile critical configurations
• Computational complexity of the avalanche problem for one dimensional decreasing sandpiles
• On the complexity of sandpile critical avalanches
• New Computational Paradigms
• Embedding arbitrary Boolean circuits into fungal automata
• On the predictability of the abelian sandpile model
• Embedding arbitrary Boolean circuits into fungal automata
• Timed prediction problem for sandpile models

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)