Computing the Difficulty of Critical Bootstrap Percolation Models is NP-hard

Hartarsky, Ivailo and Mezei, Tamás Róbert (2020) Computing the Difficulty of Critical Bootstrap Percolation Models is NP-hard. SIAM JOURNAL ON DISCRETE MATHEMATICS, Submit. pp. 1-13. ISSN 0895-4801

Preview

Text bootstrap-np-hard.pdf Download (474kB) | Preview

Abstract

Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three 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 combinatorial quantity called `difficulty', so the subject seemed closed up to finding sharper results. In this paper we prove that computing the difficulty of a critical model is NP-hard and exhibit an algorithm to determine it, in contrast with the upcoming result of Balister, Bollobás, Morris and Smith on undecidability in higher dimensions. The proof of NP-hardness is achieved by a reduction to the Set Cover problem.

Actions (login required)

Edit Item