The computational complexity of sandpiles

DOI10.1023/A:1004524500416zbMath0964.82037arXivcond-mat/9808183MaRDI QIDQ1308079

Martin Nilsson Jacobi, Moore, Cristopher

Publication date: 22 November 1999

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/9808183

zbMATH Keywords

computational complexitynonlinear systemsparallel computationcellular automataself-organized criticalityBoolean circuitsAbelian sandpile

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Related Items (max. 100)

Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models ⋮ Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three ⋮ Computational Complexity of Biased Diffusion-Limited Aggregation ⋮ Crossing information in two-dimensional sandpiles ⋮ On the sandpile group of regular trees ⋮ A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton ⋮ Kadanoff sand pile model. Avalanche structure and wave shape ⋮ On Goles' universal machines: a computational point of view ⋮ Embedding arbitrary Boolean circuits into fungal automata ⋮ Abelian networks. II: Halting on all inputs ⋮ Laplacian growth, sandpiles, and scaling limits ⋮ Computational universality of fungal sandpile automata ⋮ Strong emergence of wave patterns on Kadanoff sandpiles ⋮ On the complexity of sandpile critical avalanches ⋮ The Complexity of Three-Dimensional Critical Avalanches ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ Parallel dynamics and computational complexity of the Bak-Sneppen model ⋮ From sandpiles to sand automata ⋮ Abelian Networks I. Foundations and Examples ⋮ On the Complexity of Sandpile Prediction Problems ⋮ Abelian Logic Gates ⋮ Sandpile toppling on Penrose tilings: identity and isotropic dynamics ⋮ On fungal automata ⋮ CHOOSEY HOT SAND: REFLECTION OF GRAIN SENSITIVITY ON PATTERN MORPHOLOGY ⋮ HOW SIZE OF TARGET AVALANCHES INFLUENCES PREDICTION EFFICIENCY ⋮ Polynomial ideals for sandpiles and their Gröbner bases

This page was built for publication: The computational complexity of sandpiles