Abstract
The computational complexity of predicting sandpiles on Z2 is not settled yet, neither for von Neumann nor for Moore neighborhood (is it in NC? is it P-complete?). In this work we study the sandpile model considering all the 256 possible sub-neighborhoods within the Moore neighborhood. Surprisingly, we found that 12 of them have a P-complete prediction problem, while for the remaining 244 neighborhoods, we prove that they do not admit a crossover gate, i.e., for them, it is impossible to cross information, if the bit of information is the presence (or absence) of an avalanche.
Original language | English |
---|---|
Journal | Natural Computing |
DOIs | |
State | Accepted/In press - 2024 |
Externally published | Yes |
Keywords
- Computational complexity
- Discrete dynamical system
- Sandpile models