The complexity of the asynchronous prediction of the majority automata
Goles
E
author
Montealegre
P
author
2020
We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a non-zero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the two-dimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NP-Complete.
Majority automata
Cellular automata
Prediction problem
Asynchronous updating
Computational complexity
Parallel algorithms
Bootstrap percolation
NP-Completeness
exported from refbase (show.php?record=1124), last updated on Thu, 14 Jan 2021 13:13:51 -0300
text
10.1016/j.ic.2020.104537
Goles+Montealegre2020
Information and Computation
Inf. Comput.
2020
continuing
periodical
academic journal
274
SI
0890-5401