In 1999, Moore and Nilsson [1] demonstrated that, in lattice graphs of dimension d ≥ 3, the problem of predicting the state of a sandpile after n time steps is polynomial time (P) complete, leaving open the case for d = 2. While Gajardo and Goles do not completely settle the d = 2 problem, their brief note rules out one approach involving the simulation of monotone circuits in the traditional sandpile model. Specifically, it is impossible for signals in non-planar circuits to cross without interference when such signals are simulated by a sandpile avalanche process propagating within a background of quiescent cells.

The proof is simple and intuitive. Their results are valid for the four-neighbor von Neumann and the eight-neighbor Moore neighborhood models. However, the authors temper these findings by showing that, in a two-dimensional sandpile model using an extended von Neumann neighborhood of radius two, signal crossover can be successfully simulated. They also stipulate that their results may not hold in simulations that take place against a non-quiescent background of cells.

A small quibble: in one of their figures the authors illustrate the sandpile action for a two-by-two grid, and show the existence of a cycle of configurations, but later they claim that adding tokens to a square grid sandpile always causes it to evolve to a quiescent configuration. From the latter remark, it seems apparent that, for finite square grids, their intention is to adopt the standard definition of an Abelian sandpile, in which sand grains can “fall off” the edges of the grid into special sink states located around the boundary, apparently contradicting the example in the figure. The paper also contains a number of misspellings and grammatical errors.