The Computational Complexity of One-Dimensional Sandpiles |
| |
| Authors: | Peter Bro Miltersen |
| |
| Affiliation: | (1) Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, DK 8200 Aarhus N, Denmark |
| |
| Abstract: | We prove that the one-dimensional sandpile prediction problem is in LOGDCFL, a subset of AC1. The previously best known upper bound on the ACi-scale was AC2. Furthermore, we prove that the one-dimensional sandpile prediction problem is hard for TC0 and thus not in AC1-ε for any constant ε > 0. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
