Resumen
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.
| Idioma original | Inglés |
|---|---|
| Publicación | Natural Computing |
| DOI | |
| Estado | Aceptada/en prensa - 2024 |
| Publicado de forma externa | Sí |
Huella
Profundice en los temas de investigación de 'Sandpiles prediction and crossover on Z2 within Moore neighborhood'. En conjunto forman una huella única.Citar esto
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver