The complexity of the asynchronous prediction of the majority automata

Eric Goles, Pedro Montealegre

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish
Article number104537
JournalInformation and Computation
StatePublished - Oct 2020
Externally publishedYes


  • Asynchronous updating
  • Bootstrap percolation
  • Cellular automata
  • Computational complexity
  • Majority automata
  • NP-Completeness
  • Parallel algorithms
  • Prediction problem


Dive into the research topics of 'The complexity of the asynchronous prediction of the majority automata'. Together they form a unique fingerprint.

Cite this