How Hard is it to Predict Sandpiles on Lattices? A Survey

Issue title: Interdisciplinary Nature of Information Processing Special Issue Dedicated to Giancarlo Mauri on the Occasion of His 70th Birthday

Guest editors: Alberto Dennunzio, Gheorghe Păun, Grzegorz Rozenberg and Claudio Zandron

Article type: Research Article

Authors: Formenti, Enrico^{a; *} | Perrot, Kévin^b

Affiliations: [a] Université Côte d’Azur, CNRS, I3S, France. enrico.formenti@unice.fr | [b] Aix-Marseille Univ., Toulon Univ., CNRS, LIS, Marseille, France. kevin.perrot@lis-lab.fr

Correspondence: [*] Address for correspondence: Université Côte d’Azur, CNRS, I3S, France

Abstract: Since their introduction in the 80s, sandpile models have raised interest for their simple definition and their surprising dynamical properties. In this survey we focus on the computational complexity of the prediction problem, namely, the complexity of knowing, given a finite configuration c and a cell x in c, if cell x will eventually become unstable. This is an attempt to formalize the intuitive notion of “behavioral complexity” that one easily observes in simulations. However, despite many efforts and nice results, the original question remains open: how hard is it to predict the two-dimensional sandpile model of Bak, Tang and Wiesenfeld?

DOI: 10.3233/FI-2020-1879

Journal: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 189-219, 2020