Two Notes on the Computational Complexity of One-Dimensional Sandpiles
DOI:
https://doi.org/10.7146/brics.v6i3.20060Abstract
We prove that the one-dimensional sandpile prediction problem isin 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.
Downloads
Published
1999-01-03
How to Cite
Miltersen, P. B. (1999). Two Notes on the Computational Complexity of One-Dimensional Sandpiles. BRICS Report Series, 6(3). https://doi.org/10.7146/brics.v6i3.20060
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.