文章基本信息
- 标题：Two Notes on the Computational Complexity of One-Dimensional Sandpiles
- 本地全文：下载
- 作者：Peter Bro Miltersen
- 期刊名称：BRICS Report Series
- 印刷版ISSN：0909-0878
- 出版年度：1999
- 卷号：6
- 期号：3
- 出版社：Aarhus University
- 摘要：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.
