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 (http://ficpubs.uai.cl/show.php?record=1124), last updated on Mon, 30 Mar 2020 14:44:20 +0000
text
10.1016/j.ic.2020.104537
Goles+Montealegre2020
Information and Computation
Inform. Comput.
2020
continuing
periodical
academic journal
to appear
0890-5401