• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Complexity of two-dimensional bootstrap percolation difficulty: algorithm and NP-hardness

Thumbnail
View/Open
1809.01525_(1).pdf (399.6Kb)
Date
2020
Dewey
Analyse
Sujet
decidable; bootstrap percolation; critical models; difficulty; complexity; NP-hard
Journal issue
SIAM Journal on Discrete Mathematics
Volume
34
Number
2
Publication date
06-2020
Article pages
1444-1459
Publisher
SIAM - Society for Industrial and Applied Mathematics
DOI
http://dx.doi.org/10.1137/19M1239933
URI
https://basepub.dauphine.fr/handle/123456789/21222
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Hartarsky, Ivailo
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
66 Département de Mathématiques et Applications - ENS Paris [DMA]
Mezei, Tamás Róbert
187934 Alfréd Rényi Institute of Mathematics
Type
Article accepté pour publication ou publié
Abstract (EN)
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.