The complexity of the bootstraping percolation and other problems

DOI10.1016/J.TCS.2012.08.001MaRDI QIDQ393154zbMATH OpenOpenAlexFDO

Authors Ioan Todinca, Eric Goles, Pedro Montealegre-Barba

Publication date 16 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.08.001

zbMATH Keywords

computational complexityparallel algorithmsbootstrapping percolationmajority functionsP-completeness

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• PSPACE-completeness of majority automata networks
• The complexity of the asynchronous prediction of the majority automata
• Computational complexity of threshold automata networks under different updating schemes
• The complexity of the majority rule on planar graphs
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1241089 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• On dissemination thresholds in regular and irregular graph classes
• Random disease on the square grid
• Small Alliances in Graphs

Cited in

(29)

• Majority rule cellular automata
• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
• On the complexity of asynchronous freezing cellular automata
• Dynamics of neural networks over undirected graphs
• Linear algebra and bootstrap percolation
• Symmetrizable Boolean networks
• Amoebae for clustering: a bio-inspired cellular automata method for data classification
• Computing the probability of getting infected: on the counting complexity of bootstrap percolation
• Sandpile toppling on Penrose tilings: identity and isotropic dynamics
• On the parameterized complexity of freezing dynamics
• Eric Goles
• Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata
• Intrinsic universality in automata networks. II: Glueing and gadgets
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• The complexity of the majority rule on planar graphs
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• On the impact of treewidth in the computational complexity of freezing dynamics
• PSPACE-completeness of majority automata networks
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• On the complexity of the stability problem of binary freezing totalistic cellular automata
• The complexity of the asynchronous prediction of the majority automata
• A cube dismantling problem related to bootstrap percolation
• Cold dynamics in cellular automata: a tutorial
• On the complexity of two-dimensional signed majority cellular automata
• Computational Complexity of Biased Diffusion-Limited Aggregation
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models
• scientific article; zbMATH DE number 6302977 (Why is no real title available?)
• Computational complexity of threshold automata networks under different updating schemes

This page was built for publication: The complexity of the bootstraping percolation and other problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393154)