The complexity of the bootstraping percolation and other problems

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.