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

DOI10.1137/19M1239933MaRDI QIDQ5854892zbMATH OpenOpenAlexFDO

Authors 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

bootstrap percolationcomplexitycritical modelsdecidabilitydifficultyNP-hardness

Mathematics Subject Classification ID

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

Abstract: Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three rough universality classes, the most studied being the `critical' one. For this class the scaling of the quantity of greatest interest -- the critical probability -- was determined by Bollob'as, Duminil-Copin, Morris and Smith in terms of a simply defined combinatorial quantity called `difficulty', so the subject seemed closed up to finding sharper results. However, the computation of the difficulty, was never considered. In this paper we provide the first algorithm to determine this quantity, which is, surprisingly, not as easy as the definition leads to thinking. The proof also provides some explicit upper bounds, which are of use for bootstrap percolation. On the other hand, we also prove the negative result that computing the difficulty of a critical model is NP-hard. This two-dimensional picture contrasts with an upcoming result of Balister, Bollob'as, Morris and Smith on uncomputability in higher dimensions. The proof of NP-hardness is achieved by a technical reduction to the Set Cover problem.

Recommendations

• The complexity of the bootstraping percolation and other problems
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• scientific article; zbMATH DE number 6302977
• On percolation and NP-hardness
• On percolation and \(\mathcal{NP}\)-hardness
• The time of bootstrap percolation in two dimensions
• A sharper threshold for bootstrap percolation in two dimensions
• On \(K_{2, t}\)-bootstrap percolation

Cites work

• Bootstrap percolation, and other automata
• First passage times for threshold growth dynamics on \(\mathbb{Z}^ 2\)
• Higher order corrections for anisotropic bootstrap percolation
• scientific article; zbMATH DE number 1444756 (Why is no real title available?)
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• Metastability effects in bootstrap percolation
• Monotone cellular automata in a random environment
• Reducibility among combinatorial problems
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Slow convergence in bootstrap percolation
• Subcritical \(\mathcal{U}\)-bootstrap percolation models have non-trivial phase transitions
• The second term for two-neighbour bootstrap percolation in two dimensions
• The sharp threshold for the Duarte model
• Universality for critical KCM: infinite number of stable directions

Cited in

(5)

• \(\mathcal{U}\)-bootstrap percolation: critical probability, exponential decay and applications
• The \(d\)-dimensional bootstrap percolation models with axial neighbourhoods
• Sharp metastability transition for two-dimensional bootstrap percolation with symmetric isotropic threshold rules
• Two-dimensional supercritical growth dynamics with one-dimensional nucleation
• Universality for monotone cellular automata

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

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