Computational Complexity of the Stability Problem for Elementary Cellular Automata
Eric Goles, Fabiola Lobos, Pedro Montealegre, Eurico L.P. Ruivo and Pedro P.B. De Oliveira
Given an elementary cellular automaton and a cell v, we define the stability decision problem as the determination of whether or not the state of cell v will ever change, at least once, during the time evolution of the rule, over a finite input configuration. Here, we perform the study of the entire elementary cellular automata rule space, for the two possible decision cases of the problem, namely, changes in v from state 0 to 1 (0 → 1), and the other way round (1 → 0). Out of the 256 elementary cellular automata, we show that for all of them, at least one of the two decision problems is in the NC complexity class.
Keywords: One-dimensional cellular automata, elementary cellular automata, computational complexity, stability problem, decision problem