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 
Available as PostScript, PDF, DVI.
|
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 Available as PostScript, PDF, DVI. |