The complexity of the bootstraping percolation and other problems

Eric Goles, Pedro Montealegre-Barba, Ioan Todinca

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)73-82
Number of pages10
JournalTheoretical Computer Science
Volume504
DOIs
StatePublished - 2013
Externally publishedYes

Keywords

  • Bootstrap percolation
  • Computational complexity
  • Majority functions
  • P-Completeness
  • Parallel algorithms

Fingerprint

Dive into the research topics of 'The complexity of the bootstraping percolation and other problems'. Together they form a unique fingerprint.

Cite this