TY - JOUR

T1 - The complexity of the asynchronous prediction of the majority automata

AU - Goles, Eric

AU - Montealegre, Pedro

N1 - Funding Information:
Research founded by ECOS-CONICYT C16E01 (E.G.), CONICYT + PAI + CONVOCATORIA NACIONAL SUBVENCÓIN A INSTALACIÓN EN LA ACADEMIA CONVOCATORIA AÑO 2017 + PAI77170068 (P.M.), FONDECYT 11190482 (P.M.), and CONICYT via Programa Regional STIC-AmSud (CoDANet) cód. 19-STIC-03 (E.G. and P.M.).
Publisher Copyright:
© 2020 Elsevier Inc.

PY - 2020/10

Y1 - 2020/10

N2 - 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.

AB - 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.

KW - Asynchronous updating

KW - Bootstrap percolation

KW - Cellular automata

KW - Computational complexity

KW - Majority automata

KW - NP-Completeness

KW - Parallel algorithms

KW - Prediction problem

UR - http://www.scopus.com/inward/record.url?scp=85080975900&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104537

DO - 10.1016/j.ic.2020.104537

M3 - Article

AN - SCOPUS:85080975900

VL - 274

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104537

ER -