×

Complexity of two-dimensional bootstrap percolation difficulty: algorithm and NP-hardness. (English) Zbl 1462.68070

Summary: 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ás, 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ás, Morris, and Smith on uncomputability in higher dimensions. The proof of NP-hardness is achieved by a technical reduction to the Set Cover problem.

MSC:

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

References:

[1] M. Aizenman and J. L. Lebowitz, Metastability effects in bootstrap percolation, J. Phys. A, 21 (1988), pp. 3801-3813, https://doi.org/10.1088/0305-4470/21/19/017. · Zbl 0656.60106
[2] P. Balister, B. Bollobás, R. Morris, and P. Smith, Uncomputability of the Percolation Threshold for Monotone Cellular Automata, in preparation.
[3] P. Balister, B. Bollobás, M. Przykucki, and P. Smith, Subcritical \(\mathcal{U} \)-bootstrap percolation models have non-trivial phase transitions, Trans. Amer. Math. Soc., 368 (2016), pp. 7385-7411, https://doi.org/10.1090/tran/6586. · Zbl 1342.60159
[4] B. Bollobás, H. Duminil-Copin, R. Morris, and P. Smith, The sharp threshold for the Duarte model, Ann. Probab., 45 (2017), pp. 4222-4272, https://doi.org/10.1214/16-AOP1163. · Zbl 1454.60141
[5] B. Bollobás, H. Duminil-Copin, R. Morris, and P. Smith, Universality of two-dimensional critical cellular automata, Proc. Lond. Math. Soc. (3), to appear.
[6] B. Bollobás, P. Smith, and A. Uzzell, Monotone cellular automata in a random environment, Combin. Probab. Comput., 24 (2015), pp. 687-722, https://doi.org/10.1017/S0963548315000012. · Zbl 1371.60170
[7] J. Chalupa, P. L. Leath, and G. R. Reich, Bootstrap percolation on a Bethe lattice, J. Phys. C, 12 (1979), pp. L31-L35, https://doi.org/10.1088/0022-3719/12/1/008.
[8] H. Duminil-Copin and A. Holroyd, Finite Volume Bootstrap Percolation with Balanced Threshold Rules on \(Z^2, 2012\), preprint, http://www.ihes.fr/ duminil/.
[9] H. Duminil-Copin, A. C. D. van Enter, and T. Hulshof, Higher order corrections for anisotropic bootstrap percolation, Probab. Theory Related Fields, 172 (2018), pp. 191-243, https://doi.org/10.1007/s00440-017-0808-7. · Zbl 1404.60149
[10] J. Gravner and D. Griffeath, First passage times for threshold growth dynamics on Z2, Ann. Probab., 24 (1996), pp. 1752-1778, https://doi.org/10.1214/aop/1041903205. · Zbl 0872.60077
[11] J. Gravner and D. Griffeath, Scaling laws for a class of critical cellular automaton growth rules, in Random Walks (Budapest, 1998), Bolyai Soc. Math. Stud. 9, János Bolyai Math. Soc., Budapest, 1999, pp. 167-186. · Zbl 0949.68111
[12] J. Gravner and A. E. Holroyd, Slow convergence in bootstrap percolation, Ann. Appl. Probab., 18 (2008), pp. 909-928, https://doi.org/10.1214/07-AAP473. · Zbl 1141.60062
[13] I. Hartarsky, \( \mathcal{U} \)-Bootstrap Percolation: Critical Probability, Exponential Decay and Applications, preprint, 2018, https://arxiv.org/abs/1806.11405. · Zbl 1409.60143
[14] I. Hartarsky, L. Marêché, and C. Toninelli, Universality for critical KCM: Infinite number of stable directions, Probab. Theory Related Fields, (2020), https://doi.org/10.1007/s00440-020-00976-9. · Zbl 1464.60081
[15] I. Hartarsky and R. Morris, The second term for two-neighbour bootstrap percolation in two dimensions, Trans. Amer. Math. Soc., 372 (2019), pp. 6465-6505, https://doi.org/10.1090/tran/7828. · Zbl 1455.60130
[16] A. E. Holroyd, Sharp metastability threshold for two-dimensional bootstrap percolation, Probab. Theory Related Fields, 125 (2003), pp. 195-224, https://doi.org/10.1007/s00440-002-0239-x. · Zbl 1042.60065
[17] R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. Miller, J. W. Thatcher, and J. D. Bohlinger, eds., The IBM Research Symposia Series, Plenum, New York, 1972, pp. 85-103. · Zbl 1467.68065
[18] R. Morris, Bootstrap percolation, and other automata, European J. Combin., 66 (2017), pp. 250-263, https://doi.org/10.1016/j.ejc.2017.06.024. · Zbl 1376.82090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.