Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness

DOI10.1137/19M1239933zbMath1462.68070arXiv1809.01525OpenAlexW2914817568MaRDI QIDQ5854892

Ivailo Hartarsky, Tamás Róbert Mezei

Publication date: 12 March 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.01525

zbMATH Keywords

complexitydecidabilityNP-hardnessbootstrap percolationdifficultycritical models

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

\(\mathcal{U}\)-bootstrap percolation: critical probability, exponential decay and applications

Cites Work

• Unnamed Item
• First passage times for threshold growth dynamics on \(\mathbb{Z}^ 2\)
• The sharp threshold for the Duarte model
• Slow convergence in bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Higher order corrections for anisotropic bootstrap percolation
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• Universality for critical KCM: infinite number of stable directions
• Bootstrap percolation, and other automata
• Subcritical $\mathcal {U}$-bootstrap percolation models have non-trivial phase transitions
• Metastability effects in bootstrap percolation
• Reducibility among Combinatorial Problems
• The second term for two-neighbour bootstrap percolation in two dimensions
• Monotone Cellular Automata in a Random Environment

This page was built for publication: Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness