TY - JOUR
T1 - Freezing sandpiles and Boolean threshold networks
T2 - Equivalence and complexity
AU - Goles, Eric
AU - Montealegre, Pedro
AU - Perrot, Kévin
N1 - Publisher Copyright:
© 2021 Elsevier Inc.
PY - 2021/4
Y1 - 2021/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85099191098&partnerID=8YFLogxK
U2 - 10.1016/j.aam.2020.102161
DO - 10.1016/j.aam.2020.102161
M3 - Article
AN - SCOPUS:85099191098
SN - 0196-8858
VL - 125
JO - Advances in Applied Mathematics
JF - Advances in Applied Mathematics
M1 - 102161
ER -