TY - JOUR
T1 - The complexity of the bootstraping percolation and other problems
AU - Goles, Eric
AU - Montealegre-Barba, Pedro
AU - Todinca, Ioan
N1 - Funding Information:
The first and second authors’ work was partially supported by Fondecyt 1100003 (Eric Goles, Pedro Montealegre-Barba), BASAL-CMM (Eric Goles), and Anillo ACT-88 (Eric Goles, Pedro Montealegre-Barba). The author’s research was partially done while visiting the LIFO, Université d’Orléans.
PY - 2013
Y1 - 2013
N2 - We study the problem of predicting the state of a vertex in automata networks, where the state at each site is given by the majority function over its neighborhood. We show that for networks with maximum degree greater than 5 the problem is P-Complete, simulating a monotone Boolean circuit. Then, we show that the problem for networks with no vertex with degree greater than 4 is in NC, giving a fast parallel algorithm. Finally, we apply the result to the study of related problems.
AB - We study the problem of predicting the state of a vertex in automata networks, where the state at each site is given by the majority function over its neighborhood. We show that for networks with maximum degree greater than 5 the problem is P-Complete, simulating a monotone Boolean circuit. Then, we show that the problem for networks with no vertex with degree greater than 4 is in NC, giving a fast parallel algorithm. Finally, we apply the result to the study of related problems.
KW - Bootstrap percolation
KW - Computational complexity
KW - Majority functions
KW - P-Completeness
KW - Parallel algorithms
UR - http://www.scopus.com/inward/record.url?scp=84885181137&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.08.001
DO - 10.1016/j.tcs.2012.08.001
M3 - Article
AN - SCOPUS:84885181137
SN - 0304-3975
VL - 504
SP - 73
EP - 82
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -