Complexity of Fungal Automaton Prediction
It provides a complexity classification for a nature-inspired computational model, identifying a P-complete case that may interest theoretical computer scientists.
The paper studies the computational complexity of predicting fungal automata dynamics, finding that most rules are efficiently predictable in non-deterministic logspace, but the freezing majority rule at radius 1.5 is P-complete.
Fungal automata are a nature-inspired computational model, where a rule is alternatively applied verticaly and horizontaly. In this work we study the computational complexity of predicting the dynamics of all fungal freezing totalistic one-dimentional rules of radius $1$, exhibiting various behaviors. Despite efficiently predictable in most cases (with non-deterministic logspace algorithms), a non-linear rule is left open to characterize. We further explore the freezing majority rule (which is totalistic), and prove that at radius $1.5$ it becomes $\mathbf{P}$-complete to predict.