On the complexity of the generalized Q2R automaton
Eric Goles, Marco Montalva-Medel, Pedro Montealegre, Martín Ríos-Wilson · arXiv (Cornell University) · 2021
We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is \textbf{P}-Hard.