Embedding Boolean Circuits into Fungal Sandpile Automata with Arbitrary Update Sequences
\footnotetextA{Some of the results in this article were presented at MCU 2026.} The sandpile automata of Bak, Tang, and Wiesenfeld [Phys.\Rev.\Lett., 1987] are a simple model for particle diffusion in space. A fundamental problem related to the complexity of the model is predicting its evolution in the parallel setting. Despite decades of effort, a classification of this problem for two-dimensional sandpile automata remains outstanding. Fungal sandpile automata were recently proposed by Goles et al.~[Phys.\Lett.\ A, 2020] as a spin-off of the model in which diffusion occurs either in horizontal ($H$) or vertical ($V$) direction according to a so-called update scheme. Goles et al.~proved that the prediction problem for this model with the update scheme $H^4V^4$ is $\P$-complete. This result was subsequently improved by Modanese and Worsch [Algorithmica, 2024], who showed the problem is $\P$-complete also for the simpler update scheme $HV$. In this work, we complete the characterization and prove the prediction problem is $\P$-complete for any update scheme containing both $H$ and $V$ at least once.
Authors
- Thomas Worsch
- Augusto Modanese (ORCID: https://orcid.org/0000-0003-0518-8754)
- Martín Ríos-Wilson
- Domingo Ruiz-Tala
- Eric Goles
Institutions
- Karlsruhe Institute of Technology (DE)
- Adolfo Ibáñez University (CL)
- Helmholtz Center for Information Security (DE)
- University of Chile (CL)
Publication Details
- Journal
- Research Square
- Published
- 2026-11-18
- DOI
- https://doi.org/10.21203/rs.3.rs-11589827/v1
- Primary Topic
- Cellular Automata and Applications
- Type
- preprint