Sandpiles prediction and crossover on Z2 within Moore neighborhood

Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
JournalNatural Computing
DOIs
StateAccepted/In press - 2024
Externally publishedYes

Keywords

  • Computational complexity
  • Discrete dynamical system
  • Sandpile models

Fingerprint

Dive into the research topics of 'Sandpiles prediction and crossover on Z2 within Moore neighborhood'. Together they form a unique fingerprint.

Cite this