Computational Complexity of Avalanches in the Kadanoff Sandpile Model

• Autorzy: Formenti E. , Goles E. , Martin B.
• Języki publikacji: EN

Abstrakty

EN

This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for one-dimensional sandpiles and P-complete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak’s model of two-dimensional sandpiles.

Słowa kluczowe

EN

Kadanoff Sandpile Model; Bak Sandpile Model; Sandpiles Models; complexity; discrete dynamical system; self-organized criticality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 115, nr 1
• Strony: 107--124
• Opis fizyczny: Bibliogr. 16 poz., rys., wykr.

Twórcy

autor

Formenti E.

autor

Goles E.

autor

Martin B.

• Universite Nice–Sophia Antipolis, I3S, UMR 6070 CNRS, 2000 route des Lucioles, BP 121, F-06903 Sophia Antipolis Cedex,

Bibliografia

• [1] Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality, Phys. Rev. A, 38(1), 1988, 364-374.
• [2] Cervelle, J., Formenti, E., Masson, B.: From sandpiles to sand automata, Theor. Comput. Sci., 381(1-3), 2007, 1-28.
• [3] Dennunzio, A., Guillon, P., Masson, B.: Sand automata as cellular automata, Theor. Comput. Sci., 410(38-40), 2009, 3962-3974.
• [4] Duchi, E., Mantaci, R., Phan, H. D., Rossin, D.: Bidimensional sand pile and ice pile models, Pure Math.Appl. (PU.M.A.), 17(1-2), 2006, 71-96.
• [5] Gajardo, A., Goles, E.: Crossing information in two dimensional sand piles, Theoretical Computer Science, 369(1-3), 2006, 463-469.
• [6] Goldschlager, L.: The monotone and planar circuit value problems are log space complete for P, ACM sigact news, 9(2), 1977, 25-29.
• [7] Goles, E., Kiwi, M.: Sand pile dynamics in one dimensional bounded lattice, Cellular Automata and Cooperative Systems (N. Boccara et al, Ed.), 396, Ecole d'Hiver, Les Houches, Kluwer, 1993.
• [8] Goles, E., Margenstern, M.: Sand piles as a universal computer, Journal of Modern Physics-C, 7(2), 1996, 113-122.
• [9] Goles, E., Margenstern, M.: Universality of the chip firing game on graphs, Theoretical Computer Science, 172, 1997, 121-134.
• [10] Goles, E., Morvan, M., Phan, H. D.: Sand piles and order structure of integer partitions, Discrete Applied Mathematics, 117, 2002, 51-64.
• [11] Goles Ch., E., Morvan, M., Phan, H. D.: The structure of a linear chip firing game and related models, Theor. Comput. Sci., 270(1-2), 2002, 827-841.
• [12] Greenlaw, R., Hoover, H. J., Ruzzo, W. L.: Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, USA, 1995, ISBN 0-19-508591-4.
• [13] Kadanoff, L., Nagel, S.,Wu, L., Zhou, S.: Scaling and universality in avalanches, Phys. Rev. A, 39(12), 1989, 6524-6537.
• [14] Miltersen, P. B.: The computational complexity of one-dimensional sandpiles, Theory of Computing Systems, 41, 2007, 119-125.
• [15] Moore, C., Nilsson, M.: The computational complexity of sandpiles, Journal of statistical physics, 96(1-2), 1999, 205-224.
• [16] Perrot, K., Rémila, E.: Avalanche structure in the Kadanoff sand pile model, LATA, 6638, Springer Verlag, 2011.