Two Notes on the Computational Complexity of One-Dimensional Sandpiles

Authors

  • Peter Bro Miltersen

DOI:

https://doi.org/10.7146/brics.v6i3.20060

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.

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