Two Notes on the Computational Complexity of One-Dimensional Sandpiles
Peter Bro Miltersen
February 1999
Abstract:
We prove that the one-dimensional sandpile prediction problem
is in . The best previously known upper bound on the
-scale was . We also prove that the
problem is not in for any constant