TY - JOUR
T1 - Freezing sandpiles and Boolean threshold networks
T2 - Equivalence and complexity
AU - Goles, Eric
AU - Montealegre, Pedro
AU - Perrot, Kévin
N1 - Funding Information:
This research was partially supported by ANID via PAI + Convocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 (P.M.), FONDECYT 11190482 (P.M.), FONDECYT 1200006 (E.G., P.M.), STIC- AmSud CoDANet project 88881.197456/2018-01 (E.G., P.M., K.P.), ANR-18-CE40-0002 FANs (K.P.).
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 -