The complexity of the bootstraping percolation and other problems

Eric Goles, Pedro Montealegre-Barba, Ioan Todinca

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

22 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)73-82
Número de páginas10
PublicaciónTheoretical Computer Science
Volumen504
DOI
EstadoPublicada - 2013
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'The complexity of the bootstraping percolation and other problems'. En conjunto forman una huella única.

Citar esto