Two Notes on the Computational Complexity of One-Dimensional Sandpiles
AbstractWe prove that the one-dimensional sandpile prediction problem is
in AC1. The previously best known upper bound on the ACi-scale
was AC2. We also prove that it is not in AC1−epsilon for any constant
epsilon > 0.
How to Cite
Miltersen, P. (1999). Two Notes on the Computational Complexity of One-Dimensional Sandpiles. BRICS Report Series, 6(3). https://doi.org/10.7146/brics.v6i3.20060
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.