The sandpile automata of Bak, Tang, and Wiesenfeld (Phys. Rev. Lett., 1987) are a simple model for the diffusion of particles 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 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) directions 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 \textbf{P}-complete. This result was subsequently improved by Modanese and Worsch (Algorithmica, 2024), who showed the problem is \textbf{P}-complete also for the simpler updatenscheme HV. In this work, we fill in the gaps and prove that the prediction problem is \textbf{P}-complete for any update scheme that contains both H and V at least once.
MCU 2026
2026-07-27
2026-06-24