Two Notes on the Computational Complexity of One-Dimensional Sandpiles

  • Peter Bro Miltersen

Abstract

We 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.
Published
1999-01-03
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