The computational complexity of one-dimensional sandpiles

DOI10.1007/S00224-006-1341-8MaRDI QIDQ2642904zbMATH OpenOpenAlexFDO

Authors Peter Bro Miltersen

Publication date 6 September 2007

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-006-1341-8

zbMATH Keywords

sandpile prediction problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• New Computational Paradigms
• On the complexity of sandpile prediction problems
• The computational complexity of sandpiles
• How hard is it to predict sandpiles on lattices? A survey
• Computational complexity of avalanches in the Kadanoff sandpile model

Cited in

(14)

• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• On graph parameters guaranteeing fast sandpile diffusion
• On the complexity of sandpile prediction problems
• On the complexity of the Abelian sandpile model: communication complexity and statistical mechanics
• Computational complexity of avalanches in the Kadanoff sandpile model
• Sandpile prediction on a tree in near linear time
• How hard is it to predict sandpiles on lattices? A survey
• Strong emergence of wave patterns on Kadanoff sandpiles
• On the complexity of sandpile critical avalanches
• Computational Complexity of the Avalanche Problem on One Dimensional Kadanoff Sandpiles
• New Computational Paradigms
• Random walks, electric networks and the transience class problem of sandpiles
• Embedding arbitrary Boolean circuits into fungal automata
• Embedding arbitrary Boolean circuits into fungal automata

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

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