Abstract
In this paper we prove that the avalanche problem for the Kadanoff sandpile model (KSPM) is P-complete for two-dimensions. Our proof is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with configurations in KSPM. The proof is also related to the known prediction problem for sandpile which is in NC for one-dimensional sandpiles and is P-complete for dimension 3 or greater. The computational complexity of the prediction problem remains open for two-dimensional sandpiles.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of JAC 2010 - Journees Automates Cellulaires |
| Pages | 121-132 |
| Number of pages | 12 |
| State | Published - 2010 |
| Externally published | Yes |
| Event | 2nd Symposium on Cellular Automata - Journees Automates Cellulaires, JAC 2010 - Turku, Finland Duration: 15 Dec 2010 → 17 Dec 2010 |
Publication series
| Name | Proceedings of JAC 2010 - Journees Automates Cellulaires |
|---|---|
| Volume | 13 |
Conference
| Conference | 2nd Symposium on Cellular Automata - Journees Automates Cellulaires, JAC 2010 |
|---|---|
| Country/Territory | Finland |
| City | Turku |
| Period | 15/12/10 → 17/12/10 |