Two Notes on the Computational Complexity of One-Dimensional Sandpiles

Peter Bro Miltersen

February 1999


We prove that the one-dimensional sandpile prediction problem is in tex2html_wrap_inline25. The best previously known upper bound on the tex2html_wrap_inline27-scale was tex2html_wrap_inline29. We also prove that the problem is not in tex2html_wrap_inline31 for any constant tex2html_wrap_inline33

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.