The complexity of the bootstraping percolation and other problems

Eric Goles; Pedro Montealegre-Barba; Ioan Todinca

doi:10.1016/j.tcs.2012.08.001

The complexity of the bootstraping percolation and other problems

Eric Goles
, Pedro Montealegre-Barba
, Ioan Todinca

Research output: Contribution to journal › Article › peer-review

29 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 language	English
Pages (from-to)	73-82
Number of pages	10
Journal	Theoretical Computer Science
Volume	504
DOIs	https://doi.org/10.1016/j.tcs.2012.08.001
State	Published - 2013
Externally published	Yes

Keywords

Bootstrap percolation
Computational complexity
Majority functions
P-Completeness
Parallel algorithms

Access to Document

10.1016/j.tcs.2012.08.001

Cite this

@article{cade989031b4477f8e4091495b4fb956,

title = "The complexity of the bootstraping percolation and other problems",

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.",

keywords = "Bootstrap percolation, Computational complexity, Majority functions, P-Completeness, Parallel algorithms",

author = "Eric Goles and Pedro Montealegre-Barba and Ioan Todinca",

note = "Funding Information: The first and second authors{\textquoteright} 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{\textquoteright}s research was partially done while visiting the LIFO, Universit{\'e} d{\textquoteright}Orl{\'e}ans.",

year = "2013",

doi = "10.1016/j.tcs.2012.08.001",

language = "English",

volume = "504",

pages = "73--82",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

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 - https://www.scopus.com/pages/publications/84885181137

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 -

The complexity of the bootstraping percolation and other problems

Abstract

Keywords

Access to Document

Fingerprint

Cite this