错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Sandpiles prediction and crossover on \(\mathbb {Z}^2\) within Moore neighborhood

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

摘要

The computational complexity of predicting sandpiles on \(\mathbb {Z}^2\) Z 2 is not settled yet, neither for von Neumann nor for Moore neighborhood (is it in \({\textsf{NC}}\) NC ? is it \({\textsf{P}}\) 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 \({\textsf{P}}\) 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.