Freezing sandpiles and Boolean threshold networks: Equivalence and complexity

Eric Goles, Pedro Montealegre, Kévin Perrot

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

Resumen

The NC versus P-hard classification of the prediction problem for sandpiles on the two dimensional grid with von Neumann neighborhood is a famous open problem. In this paper we make two kinds of progresses, by studying its freezing variant. First, it enables to establish strong connections with other well known prediction problems on networks of threshold Boolean functions such as majority. Second, we can highlight some necessary and sufficient elements to the dynamical complexity of sandpiles, with a surprisingly crucial role of cells with two grains.

Idioma originalInglés
Número de artículo102161
PublicaciónAdvances in Applied Mathematics
Volumen125
DOI
EstadoPublicada - abr. 2021

Huella

Profundice en los temas de investigación de 'Freezing sandpiles and Boolean threshold networks: Equivalence and complexity'. En conjunto forman una huella única.

Citar esto