# Timed Prediction Problem for Sandpile Models

Pablo Concha-Vega¹ and Kévin Perrot¹,²

¹ Aix Marseille Univ, CNRS, LIS, Marseille, France
{pablo.concha-vega,kevin.perrot}@lis-lab.fr

² Université publique, Marseille, France

**Abstract.** We investigate the computational complexity of the *timed prediction problem* in two-dimensional sandpile models. This question refines the classical *prediction problem*, which asks whether a cell *q* will eventually become unstable after adding a grain at cell *p* from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the height adjacent cells. In this paper, we introduce the *timed setting*, where the goal is to determine whether cell *q* becomes unstable *exactly* at time *t*. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.

**Keywords:** Sandpile models · Discrete dynamical system · P-completeness

## 1 Introduction

Sandpiles are the canonical example of self-organized criticality [1], a phenomenon where complex, scale-invariant behavior emerges from simple local rules without any need for fine-tuning. Originally proposed in the context of statistical physics, sandpile models have also attracted interest from the perspective of computational complexity. A central question in this context is the *prediction problem*, which asks the following: starting from a stable configuration, and choosing two specific cells *p* and *q*, is it possible that adding a single grain at cell *p* will eventually cause cell *q* to become unstable (*i.e.*, ready to topple) at some point in time? This question captures the difficulty of anticipating the long-term effects of a simple perturbation.

Early foundational work by Moore and Nilsson [12] revealed that the computational power of sandpile dynamics depends strongly on the dimension of the grid. In dimension one, they showed that the prediction problem admits a fast parallel algorithm (in $NC^3$), while in dimension three or more it is P-complete,
implying an inherent sequentiality in the dynamics. The two-dimensional case, however, remains open to this day. A significant obstacle to proving P-completeness in dimension two was identified by Gajardo and Goles [6], who showed that neither of the standard von Neumann nor Moore neighborhoods admit a crossover gate, which is a crucial component of all P-completeness proofs so far.

In a previous work [3], we systematically studied all subsets of the Moore neighborhood on the two-dimensional grid. By grouping them into equivalence classes under rotation and reflection, we identified which classes admit a *crossover*, and which do not. It follows that the former have a P-complete prediction problem, whereas the latter may be computationally easier to predict. In the present work, we extend this line of research by introducing a refined decision problem, which we call the *timed prediction problem*. This problem is similar in spirit to the original prediction problem, but with an important difference: a timestep *t* is now part of the input. More precisely, given a stable configuration, two cells *p* and *q*, and a time *t*, the question is whether adding a grain at cell *p* will cause cell *q* to become unstable after *exactly* *t* time steps.

We conduct a systematic study of the timed prediction problem across all subsets of the Moore neighborhood, following the equivalence classes approach of [3]. For each class, we seek to determine whether it admits a complete set of timed computational gadgets. Our results reveal a rich landscape: a large number of neighborhoods (planar ones) do not admit a timed crossover at all, which makes it unlikely for them to support a P-hardness reduction. On the other hand, we identify several new classes that do admit a complete timed toolkit, for which we establish the P-completeness of the timed prediction problem. A further group of neighborhoods admits a timed crossover gate, but encounters a difficulty when connecting gates consistently in time, a phenomenon we refer to as the *delay issue*. For the remaining classes, we conjecture that no timed crossover is possible.

## 2 Definitions and state of the art

**Notations.** We write $N_+ = N \setminus \{0\}$ for the set of positive integers, and use $\subset_{fin}$ to refer to finite subsets. Given any $d \in N_+$, we denote by $0^d$ the $d$-dimensional tuple consisting entirely of zeros. The Heaviside step function $H(\cdot)$ is defined by $H(\alpha) = 1$ if $\alpha \ge 0$, and $H(\alpha) = 0$ otherwise. For any $n \in N_+$, we write $[n] = \{1, \dots, n\}$ and $\llbracket n \rrbracket = \{0, \dots, n-1\}$.

**Sandpile models.** In this work, we consider sandpile dynamics restricted to two-dimensional square lattices $Z^2$. A *sandpile model* is specified by a finite neighborhood $\mathcal{N} \subset_{fin} \mathbb{Z}^2$, whose cardinality we denote by $\theta_{\mathcal{N}} = |\mathcal{N}|$. A *configuration* is a function $c: \mathbb{Z}^2 \to \mathbb{N}$ assigning to each cell $p \in \mathbb{Z}^2$ a number $c(p)$ of grains. The associated dynamics $F_{\mathcal{N}}: \mathbb{N}^{\mathbb{Z}^2} \to \mathbb{N}^{\mathbb{Z}^2}$ is defined cellwise by:

$$ \forall p \in \mathbb{Z}^d : F_{\mathcal{N}}(c)(p) = c(p) - \theta_{\mathcal{N}} \cdot H(c(p) - \theta_{\mathcal{N}}) + \sum_{p' \in \mathcal{N}} H(c(p - p') - \theta_{\mathcal{N}}). $$
<figure><img src="image_1.png" /><figcaption>Fig. 1: Example of sandpile dynamics for Moore neighborhood $\mathcal{N}_m$. The numbers indicate the amount of grains in every cell (blank is empty).</figcaption></figure>

In words, each cell reaching the threshold $\theta_{\mathcal{N}}$ topples or fires, sending one grain to each of its out-neighbors, whose relative positions are given by $\mathcal{N}$. This local rule is applied in parallel at every cell of the lattice. The most well-known neighborhoods, due to their simplicity and symmetries, are von Neumann and Moore, respectively defined as:

$$ \mathcal{N}_{\text{vn}} = \{(x, y) \in \mathbb{Z}^2 \mid |x| + |y| = 1\} \quad \text{and} \quad \mathcal{N}_{\text{m}} = \{(x, y) \in \mathbb{Z}^2 \mid 1 \le x^2 + y^2 \le 2\}. $$

See an example in Figure 1.

When it is clear from the context, we drop the subscript notations and simply denote $\theta$ and $F$ the threshold and the evolution rule. The total number of sand grains in a configuration is denoted $\mathcal{G}(c) = \sum_{p \in \mathbb{Z}^2} c(p)$, it is invariant under $F$ for any sandpile model: $\mathcal{G}(c) = \mathcal{G}(F(c))$. A configuration $c$ is *finite* when it contains a finite number of sand grains ($\mathcal{G}(c) \in \mathbb{N}$), and *stable* when no toppling occurs ($\forall p \in \mathbb{Z}^2 : c(p) < \theta$). From any finite configuration $c$, the dynamics converges to a stable configuration denoted $c^\circ = \lim_{t \to \infty} F^t(c)$ (see e.g., [5]). Note that it is customary to exclude the cell itself (at relative position $0^d$) from its neighborhood, in order to avoid “trapping” one sand grain at each cell.

We restrict our study to neighborhoods $\mathcal{N} \subset_{\text{fin}} \mathbb{Z}^2$ that span $\mathbb{Z}^2$ i.e., such that $\mathcal{N} = \{p_1, p_2, \dots, p_k\}$ and $\{a_1 \cdot p_1 + a_2 \cdot p_2 \cdots + a_k \cdot p_k \mid a_1, a_2, \dots, a_k \in \mathbb{Z}\} = \mathbb{Z}^2$. Otherwise, the dynamics splits into independent subsystems, meaning that $\mathbb{Z}^2$ can be decomposed into sublattices for which the sand contents never interact. In this case, the global behavior becomes a product of independent sandpile dynamics over lower-dimensional components. Such separability would complicate our considerations, as crossovers could trivially arise between signals evolving in disconnected sublattices.

**Prediction problems and crossovers.** The problems are formulated for each sandpile model $\mathcal{N} \subset_{\text{fin}} \mathbb{Z}^2$. The asymptotic prediction of sandpile dynamics is the problem of computing the stable configuration $c^\circ$ reached from a given configuration $c$. It is classically restricted to an input configuration $c$ which is finite and stable, and a position $p \in \mathbb{Z}^2$ on which one grain is added, and formalized as the following decision problems [5]. For any $p \in \mathbb{Z}^2$, let $1p$ be the configuration containing a unique grain at position $p$, and let $+$ denote the cell-wise addition of two configurations ($\forall p \in \mathbb{Z}^2, (c + c')(p) = c(p) + c'(p)$). It asks whether cell $q \in \mathbb{Z}^2$ topples during the evolution from $c + 1p$ to $(c + 1p)^\circ$.
### N-sandpile prediction problem (N-PRED)

Input: a finite stable configuration $c \in \mathbb{N}^{\mathbb{Z}^2}$, and two positions $p, q \in \mathbb{Z}^d$.

Question: does $\exists t \in \mathbb{N}, F^t(c+1p)(q) \ge \theta$?

We highlight the following problem, for which it is not clear yet whether it can be more difficult or less difficult than N-PRED for some sandpile models $\mathcal{N}$. It asks whether cell $q$ topples at time step $t$ during the evolution from $c+1p$.

### N-sandpile timed prediction problem (N-TIMED-PRED)

Input: a finite stable config. $c \in \mathbb{N}^{\mathbb{Z}^2}$, two positions $p, q \in \mathbb{Z}^d$, and a time $t \in \mathbb{N}$.

Question: does $F^t(c+1p)(q) \ge \theta$?

The general goal is to dichotomize the complexity of prediction problems based on the neighborhood $\mathcal{N}$: either in NC or P-complete for logspace reductions (see [10, 11] for the definitions of NC, P, and their meaning within the theory of computational complexity). It is proven in [5] that all such problems lie in P (more precisely, the quantification over $t$ can be upper bounded to a value polynomial in the size of $c$). On one hand, proofs that the problem belongs to NC typically involve either providing an efficient parallel algorithm, or reducing the problem to another one for which such an algorithm is known [5, 7, 9, 12]. On the other hand, proofs of P-completeness rely on the so-called *Banks approach* [2], which consists in reducing from *monotone circuit value problem (MCVP)* by implementing the circuit computation via chains of reactions in the sandpile dynamics. In this context, it is required to build *wires, turns, and gates, or gates, diodes and crossover gates* [8]. In turns out that all gates are usually straightforward to design, except crossover gates. The inexistence of crossover gates is therefore a strong indication that such a reduction may not be possible, but it is relative to a precise definition of crossover gate (to prove that none exist), which enforces a precise (hence restrictive) consideration of what a *wire*, or more generally a *signal*, is. This topic is of much broader interest [4].

**Definition 1 (Crossover gate).** A *crossover gate* is a rectangular subset of the lattice on which a stable configuration is set, such that it transports signals from two pairs of opposite sides, independently from each other: two wires cross each other. Given a sandpile model $\mathcal{N}$, a crossover gate of size $M \times N$ is formally defined as a configuration $g: [[M]] \times [[N]] \to \{0, \dots, \theta-1\}$ together with four cells $n, e, s, w \in ([[M]] \times [[N]]) \setminus \{(0,0), (M-1,0), (0,N-1), (M-1,N-1)\}$ not in the corners, verifying the following constraints 1–5. For convenience, we denote the four sides of the gate as $S_0 = \{(0,y) \mid y \in [[N]]\}$, $S_1 = \{(x,0) \mid x \in [[M]]\}$, $S_2 = \{(M-1,y) \mid y \in [[N]]\}$, $S_3 = \{(x,N-1) \mid x \in [[M]]\}$.

1. $n, s$ are on opposite sides, i.e. $\exists i_n, n \in S_{i_n}, \exists i_s, s \in S_{i_s}$ and $|i_n - i_s| = 2$;

2. $w, e$ are on opposite sides, i.e. $\exists i_w, w \in S_{i_w}, \exists i_e, e \in S_{i_e}$ and $|i_w - i_e| = 2$;

3. $n, e, s, w$ are on different sides, i.e. $\{i_n, i_e, i_s, i_w\} = \{0, 1, 2, 3\}$;

4. adding a grain at $n$ eventually topples $s$, but no cell on the other sides, i.e. $\exists t \in \mathbb{N}, F^t(g+1_n)(s) \ge \theta$, but $\forall p \in S_{i_w} \cup S_{i_e}, \forall t \in \mathbb{N}, F^t(g+1_n)(p) < \theta$;

5. adding a grain at $w$ eventually topples $e$, but no cell on the other sides, i.e. $\exists t \in \mathbb{N}, F^t(g+1_w)(e) \ge \theta$, but $\forall p \in S_{i_n} \cup S_{i_s}, \forall t \in \mathbb{N}, F^t(g+1_w)(p) < \theta$.
<figure><img src="image_2.png" /><figcaption>Fig. 2: Subsets of Moore neighborhood corresponding to 00001000 = 8, 01001010 = 74, 00100111 = 39, 10000111 = 135, 01111111 = 127.</figcaption></figure>

It is necessary to provide this formal definition, as we will state some im-
possibility results; however it is difficult to use in practice. In the following, no
precise reference will be made to its constituents. The main tool we will employ
is the *pair of firing graphs*, which is introduced at the beginning of Section 3.

For the timed prediction problem, a *timed crossover gate* is required. It is
the same as a crossover gate, except that all quantifications over time *t* are
bounded to a given value *T* ∈ N+ called the *delay* of the gate (which is part of
the definition of the gate). That is, when adding a grain to one side (at *n* or *w*),
the cell on the opposite side (*s* or *e*) must topple at time step *T*, and no cell on
the other sides must topple before time step *T* + 1.

3 Timed crossover among subsets of Moore

In this section we present an exhaustive study of the computational complexity
of sandpile dynamics, by considering timed prediction problems ($\mathcal{N}$-TIMED-
PRED) and timed crossover gates for every subset of the Moore neighborhood
$\mathcal{N}_m$. Observe that some of the $2^8$ subsets of $\mathcal{N}_m$ (which has 8 elements) do not
span $\mathbb{Z}^2$, and the existence of a crossover gate is invariant by rotation and axial
symmetries of the neighborhood. It reduces the number of neighborhoods to
study to 43 equivalence classes, presented in [3, Table 1].

An example of timed crossover gate is presented on Figure 3. We will show
that while some neighborhoods do not support a crossover gate, they do admit a
timed crossover gate and exhibit a P-complete timed prediction problem. It hints
at the fact that predicting the dynamics at a precise time step may be harder
than asymptotic prediction of the dynamics (the final stable configuration).

**Definition 2 (Subset of Moore neighborhood).** Let $n, ne, e, se, s, sw, w, nw$ denote the eight cardinal coordinates, starting with north and proceeding clockwise. We denote a subset of Moore neighborhood as an 8-bits string, where the $i$-th bit indicates whether the $i$-th coordinate in the list $n, e, s, w, nw, ne, se, sw$, is part of the neighborhood (bit 1), or not (bit 0). We also interpret 8-bits strings as numbers (converting them to decimal) with the least significant bit on the right, see Figure 2.

In this numbering scheme, the von Neumann neighborhood ($\mathcal{N}_{vn}$) corresponds to 11110000 (decimal 240), while the Moore neighborhood ($\mathcal{N}_m$) corresponds to 11111111 (decimal 255). Note that neighborhoods with numbers $\le 15$ consist exclusively of diagonal neighbors, and as a result, they do not span $\mathbb{Z}^2$.
<figure><img src="image_3.png" /><figcaption>Fig. 3: Example of timed crossover gate of size $10 \times 10$ for neighborhood 131 (left). The delay of the gate is 14. We picture the timestamps of each cell, following a grain addition at $n$ (center), and a grain addition at $w$ (right).</figcaption></figure>

**Section outline.** We start this section by defining timed firing graphs (Subsection 3.1), a tool that captures the timing and causal dependencies of topplings in a timed crossover. First we prove that timed crossover gates are impossible when the neighborhood is planar (Subsection 3.2). Then we exhibit timed crossover gates for many neighborhoods. For some of them we prove that $\mathcal{N}$-TIMED-PRED is P-complete (Subsection 3.3), and for others we are faced with a delay issue when trying to connect the different gates (Subsection 3.4). The results of this section are summarized in Table 1.

## 3.1 Timed firing graphs

The causal structure of topplings is captured by the concept of firing graph, introduced in [6]. It is at the basis of our reasonings in this work. Given a neighborhood $\mathcal{N}$, we say that cell $v_1$ is an in-neighbor (resp. out-neighbor) of cell $v_2$ when $(v_2 - v_1) \in \mathcal{N}$ (resp. $(v_1 - v_2) \in \mathcal{N}$). Observe that $v_1$ may be both an in-neighbor and an out-neighbor of $v_2$. In particular, this is always the case for symmetric neighborhoods, such as von Neumann $\mathcal{N}_{vn}$ and Moore $\mathcal{N}_{m}$.

**Definition 3 (Firing graphs).** Given a crossover gate $g$ on cells $n, s, w, e$ we define its two firing graphs $G_{ns}^g = (V_{ns}, A_{ns})$ and $G_{we}^g = (V_{we}, A_{we})$ as:

- $V_{ns}$ (resp. $V_{we}$) is the set of cells toppled after adding a grain at cell $n$ (resp. $w$);

- we have $(v_1, v_2) \in A_{ns}$ (resp. $A_{we}$) when $v_1, v_2 \in V_{ns}$ (resp. $V_{we}$) verify:

* $v_1$ is an in-neighbor of $v_2$ for $\mathcal{N}$, and

* $v_1$ is fired strictly before $v_2$ after adding a grain at cell $n$ (resp. $w$).

The endpoints of a firing graph are called *starting cells* ($n$ and $w$) and *ending cells* ($s$ and $e$) respectively. For every arc $(v_1, v_2)$ in a firing graph, we call $v_1$ a *predecessor* of $v_2$, and $v_2$ a *successor* of $v_1$. The transitive and reflexive closure of the predecessor (resp. successor) relationship is the *ancestor* (resp. *descendant*) relationship. By definition, a predecessor is necessarily an in-neighbor, and a successor is necessarily an out-neighbor. The firing graph captures the *effective*
<table><caption>Table 1: Summary of results exposed in Section 3.</caption><thead><tr><th>Section</th><th>3.3</th><th>3.4</th><th>3.5</th></tr><tr><th>Type</th><td>P-complete</td><td>Delay issue</td><td>Timed crossover impossibility (conjecture)</td></tr></thead><tbody><tr><th>Neighborhoods</th><td><pre>11
01101111
33
10000111
54
10010111
193
11000111
314
11010011
315
11010111</pre></td><td><pre>27
01111111
43
10001111
435
11000111
95
11000011
211
11010011
334
11011111</pre></td><td><pre>39
00100111
83
01010011
95
01011111
67
01000011
87
10000011</pre></td><td><pre>35
00100011
103
01100111
114
01110111
119
11100011
221
11110011
34
11111111</pre></td></tr></tbody></table>

causal relationships among cells within a given crossover gate, whereas the in-neighbor and out-neighbor relationships represent potential relationships.

The pair of firing graphs of a timed crossover gate may intersect (have vertices in common), because the wire in the perpendicular direction can be toppled (provided that it does so some steps behind compared to the 1 signal traversing the gate). We introduce the notion of *timed firing graphs*, which are subsets of the firing graphs. Given that the arcs of the firing graphs represent the causal relationship among toppled cells, it would be enough to discard the part not necessary to topple an ending cell, by restricting the corresponding firing graph to its ancestors. However, this inductive definition from the ending cell backwards, is not convenient for proofs by induction on the number of steps. We prefer the following definition, based on timestamps, which we denote $t_{ns} : V_{ns} \to \mathbb{N}$ and $t_{we} : V_{we} \to \mathbb{N}$ to distinguish the two firing graphs. In each firing graph, we take into account only cells toppling sufficiently early to belong to 1 signals. Recall that the timestamps of the two ending cells are equal to the delay $T$ of the gate. Let $t_{ns}(v) = +\infty$ when $t_{ns}$ is not defined for $v$. The same applies to $t_{we}$.

**Definition 4 (Timed firing graphs).** Given a timed crossover gate $g$ of delay $T \in \mathbb{N}_+$ on cells $n, s, w, e$, its two timed firing graphs are the subsets of its firing graphs, restricted to vertex sets:

$$V_{ns}^{T} = \{v \in V_{ns} | t_{ns}(v) \leq t_{we}(v)\} \text{ and } V_{we}^{T} = \{v \in V_{we} | t_{we}(v) \leq t_{ne}(v)\}.$$

It is necessary that in a timed crossover gate, each of the two ending cells belongs only to its corresponding timed firing graph. The $\leq$ comparison among timestamps aims at discarding cells that have some retard. The following Lemma generalizes Proposition 1 from [13], to the context of timed firing graphs.
**Lemma 1.** If a sandpile model $\mathcal{N}$ admits a timed crossover gate, then it also admits a timed crossover gate $g$ with timed firing graphs $G_{ns}^T = (V_{ns}^T, A_{ns}^T)$ and $G_{we}^T = (V_{we}^T, A_{we}^T)$, such that $V_{ns}^T \cap V_{we}^T = \emptyset$.

*Proof.* The proof is constructive: given a timed crossover gate $g'$ with timed firing graphs $G'_{ns} = (V'_{ns}, A'_{ns})$ and $G'_{we} = (V'_{we}, A'_{we})$, we:

1. remove all grains from vertices in the intersection $V'_{ns} \cap V'_{we}$ (which are intuitively useless), so that they do not topple anymore;

2. compensate for the missing predecessors in each timed firing graph: for each vertex in exactly one of $V'_{ns}^T$ or $V'_{we}^T$, add as many grains to it as it had predecessors in $V'_{ns}^T \cap V'_{we}^T$.

We now argue that it gives another timed crossover gate with distinct timed firing graphs. By induction on successive time steps, we have the following three simple facts. First, the vertices in $V'_{ns}^T \cap V'_{we}^T$ do not topple anymore (this uses the fact that sandpile graphs are Eulerian). Second, the vertices not in the intersection are still in their timed firing graph (thanks to the sand grains added at step 2, there is no retard in the topplings). Third, no new vertex appears in each timed firing graph, i.e. $V_{ns}^T \subseteq V'_{ns}^T$ and $V_{we}^T \subseteq V'_{we}^T$ (because the sand grains added at step 2 do not create successor relationships in the timed firing graph). Given that $n, s \in V'_{ns}^T \setminus V'_{we}^T$ and $w, e \in V'_{we}^T \cap V'_{ns}^T$, this still holds and the constructed configuration is indeed a timed crossover gate (it still performs a timed crossover of two signals), with sets of vertices $V_{ns}^T = V'_{ns}^T \setminus V'_{we}^T$ and $V_{we}^T = V'_{we}^T \setminus V'_{ns}^T$. $\square$

## 3.2 Timed crossover impossibility: planar neighborhoods

As a corollary of Lemma 1, it is impossible to have a timed crossover gate when the neighborhood is planar.

**Corollary 1.** If neighborhood $\mathcal{N}$ has a planar sandpile graph, then it does not admit a timed crossover gate.

This proves that neighborhoods 66, 74, 82, 98, 90, 106, 130, 146, 192, 200, 202, 208, 210, 226, 234, 240, 242 and 250 do not admit a timed crossover gate.

## 3.3 Timed crossover possibility: P-complete neighborhoods

Neighborhoods studied in this subsection:

<figure><img src="image_4.png" /></figure>

We now prove that some subsets of Moore neighborhood have a P-complete $\mathcal{N}$-TIMED-PRED problem. The proof is analogous to Theorem 2 from [3], but taking into account the delay of the gates.
<figure><img src="image_5.png" /><figcaption>Fig. 4: Embedding of a **MCVP** instance of fan-in and fan-out two (left) on the grid (right). Diodes (represented as ▶ and ▼) are used systematically between layers in order to enforce the flow of information (and prevent it to go backward).</figcaption></figure>

**Theorem 1.** *N-TIMED-PRED is P-complete for neighborhoods 111, 127, 135, 143, 151, 195, 199, 211, 215.*

*Proof.* For neighborhoods 135 and 143, this is a direct consequence of [3, Theorem 2], as they both have a P-complete prediction problem.

For the other neighborhoods, we prove P-completeness by reduction from monotone circuit value problem (**MCVP**) with gates of fan-in and fan-out two (problem **AM2CVP** in [10]), We consider an embedding of the monotone circuit on the two-dimensional grid (see Figure 4), and replace all the elements by the corresponding sandpile gadgets of fixed size. For each neighborhood, we present a set of gates having a uniform delay (it takes the same number of steps for a signal to traverse each gate). Let us denote $d \in \mathbb{N}_+$ this *delay*, and $z$ the peculiar delay of the starting constant 1 gate (time necessary for the single grain addition at $p$ to reach the borders of the constant 1 gate). Following Banks approach, a signal 1 is an avalanche (chain of topplings) reaching the edges of gates at time steps $(z+d \cdot T)_{T \in \mathbb{N}}$, and a signal 0 is a steady state or an avalanche reaching the edges of gates on time steps $z+d \cdot T + i$ with $i > 0$ (retards may accumulate). One can check on the layout of the **MCVP** instance on the grid (Figure 4), that following a single grain addition, all the variable signals start synchronized (with avalanches for 1 signals, and steady wires for 0 signals). The uniform delay on all gates ensures that signals keep synchronized, because gates are placed on the diagonal: the two input signals are at the same distance from the origin. Every wire follows a shortest path in the grid toward the questioned cell. The latter
therefore topples at time step $z+d \cdot U+y$, with $U$ the distance in the grid from the origin (top left cell) to the questioned cell and $y$ for its inner mechanism (precise distance to $q$), if and only if the **MCVP** outputs a signal 1.

<figure><img src="image_6.png" /><figcaption>Fig. 5: Timed crossover gates (top left), and gates (top right, with $\delta = \theta_N - 2$), or gates (top right, with $\delta = \theta_N - 1$), horizontal diode (bottom left) and vertical diode (bottom right) for neighborhoods 111 and 127 with $\gamma = \theta_N - 1$. The gates have size $10 \times 10$ and delay 12.</figcaption></figure>

The set of gates are presented as follows:

- on Figure 5 for neighborhoods 111 and 127,

- on Figure 6 for neighborhood 151,

- on Figure 7 for neighborhoods 195, 211, 215 and 199.

For each neighborhood we present a crossover gate, an and gates, an or gate, and diodes. The constant 1 gate, turns and signal-duplication are derived from the or gate. The constant 0 gate is empty. $\square$

## 3.4 Timed crossover possibility: delay issue

Neighborhoods studied in this subsection:

<figure><img src="image_7.png" /></figure>
<figure><img src="image_8.png" /><figcaption>Fig. 6: Timed crossover gate (top left), *and* gate (top right, with $\delta = 3$), *or* gate (top right, with $\delta = 4$), horizontal diode (bottom left) and horizontal diode (bottom right) for neighborhood 151. The gates have size 10 × 10 and delay 13.</figcaption></figure>

For multiple neighborhoods, we are able to construct a timed crossover gate, and even *and* and *or* gates, but we are faced with an issue when trying to plug these gates together. Timed crossover gates for neighborhoods 39, 67, 83, 87 and 95 are presented on Figure 8, and a timed crossover gate for neighborhood 131 is presented on Figure 3.

Let us focus on neighborhood 39 as an example. On Figure 9 we present an almost complete set of gates, of size 11 × 11 with delay 11. Inputs are located on the *west* and *north* borders, and outputs on the *east* and *south* borders. The north input and south output are identically located in every gate, and there are two possible locations of the west input and east output (size 11 is odd): either exactly in the middle of their respective borders (label *A* on Figure 9), or one cell above (label *B*). They are meant to be plugged alternatively to each other horizontally (adapting the construction from Figure 4), following a pattern of mono-labeled columns of gates. There are:

- wires (also *diodes*) labeled *A* and *B*,

- a *crossover* gate labeled *A*,

- an *or* gate labeled *B*,

- an *and* gate labeled *B*,

- a *constant* 1 gate labeled *B* is derived from the *or* gate,

- a *signal-duplication* gate labeled *B* is derived from the *or* gate,

- *turn* gates labeled *B* are derived from the *or* gate,
<figure><img src="image_9.png" /><figcaption>Fig. 7: Timed crossover gates (top left), and gates (top right, with $\delta = \theta_N - 2$), or gates (top right, with $\delta = \theta_N - 1$), horizontal diode (bottom left) and vertical diode (bottom right) for neighborhoods 195 (with $\gamma' = \theta_N - 1$), 199 (with $\gamma' = \theta_N - 2$), 211 (with $\gamma' = \theta_N - 1$) and 215 (with $\gamma' = \theta_N - 2$), with $\gamma = \theta_N - 1$. The gates have size 12 × 12 and delay 17.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 8: Neighborhoods next to their timed crossover gate. Each non-empty cell contains $\gamma = \theta_N - 1$ grains. The triangles indicate the direction in which the cells are toppled.</figcaption></figure>
– a *constant* 0 gate is empty (labeled *A* and *B*).

Only a pair of gates is missing: *turn* gates labeled *A*. If *turn* gates labeled *A* exist, then we can connect all these gates together following this mono-labeled column approach (using *zigzags* to switch label) and prove the P-completeness of *N*-**TIMED-PRED**. However, we show below that *turn* gates labeled *A* do not exist: the distance from the west input corresponding to label *A* to the south output is incompatible with the movements possible under a delay of 11. We do not know how to proceed with this reduction without *turn* gates labeled *A*.

<figure><img src="image_11.png" /><figcaption>Fig. 9: An almost complete set of timed gates of size 11 × 11 and delay 11 for neighborhood 39. Timed crossover gate (top left, labeled *A*), *or* gate (top right, with $\delta = 3$, labeled *B*), *and* gate (top right, with $\delta = 2$, labeled *B*), horizontal diodes (bottom left and center, resp. labeled *A* and *B*) and vertical diode (bottom right, labeled both *A* and *B*).</figcaption></figure>

The synchronization issue is explained by the fact that neighborhoods 39, 67, 83, 87, 95 and 131 are all in one of the two following cases:

– not having cell *north* nor *south* in the neighborhood,

– not having cell *west* nor *east* in the neighborhood.

Consequently, at each step of the avalanche process (chain of reaction of topplings), a signal must move along the perpendicular direction. For simplicity let
us assume that neither cell west nor east are in the neighborhood, so that a signal
must move along the y axis at each step. This induces a parity for the timestamps
of signals: they have even timestamps on the cells $X_2 = \{(x, y) \in \mathbb{Z}^2 | x \text{ is even}\}$
and odd timestamps on the other cells $\mathbb{Z}^2 \setminus X_2$, or odd timestamps on $X_2$ and
even timestamps on $\mathbb{Z}^2 \setminus X_2$.

It turns out that the *or/and* and *crossover* gates presented on Figure 9 use
a different combination of parities for the two input signals, because:

- *or/and* gates require the two signals to *meet* at synchronized timestamps,

- *crossover* gates require the two signals to *be adjacent along the y axis* at synchronized timestamps.

This leads to an incompatibility in the synchronization between those gates for
neighborhood 39. Neighborhoods 67, 83, 87 and 95 face a symmetric issue.

The case of 131 is different. It does not have the cell *west* nor *east* in the neighborhood, therefore it has a parity along the *y* axis, but the *crossover* gate requires the two signals to be adjacent along the *x* axis. So there is no apparent incompatibility. Nonetheless, we were not able to solve the synchronization issue for neighborhood 131.

**3.5 Timed crossover impossibility: conjectured**

Neighborhoods studied in this subsection:

<figure><img src="image_12.png" /></figure>

The difficulty to design a timed crossover gate for these neighborhoods lies
in the fact that it is not possible to take advantage of the diagonal neighbors
(in terms of delay) because the cell in-between the two diagonals is also an out-
neighbor. We conjecture that this prevents to construct timed crossover gates
for these neighborhoods, *i.e.* that they do not admit a timed crossover gate.

**4 Conclusions**

In this work we have considered the timed version of the sandpile prediction
problem, asking whether, following a single grain addition on a stable configu-
ration, a questionned cell will topple or not at a precise time step $t \in \mathbb{N}$ which
is part of the input. To study this problem, we have introduced the notion of
timed firing graph, and timed crossover gate. The timed crossover gate allows
for each of the two input cells to trigger an avalanche eventually toppling both
output cells, provided there is a strictly positive retard on the output signal
in the incorrect direction (not correspond to a crossing of two signal, *e.g.* from
*north* to *south* the avalanche is allowed to topple the *east* cell if the delay of the
signal from *north* to *south* is strictly smaller than the delay of the signal from
north to east). This difference of delay aims at being embedded in a reduction
from MCVP to N-TIMED-PRED problem, according to the construction
depicted on Figure 4 (which has been designed with this purpose). It requires
to have wire, turns, and or gates with adequate delays, and with input and
output cells that plug well to each other in order to keep the signals synchro-
nized. Our results are partial; among the 255 non-empty subsets of the Moore
neighborhood (the results are summarized on Table 1):

- 21 do not span $Z^2$ and are therefore not relevant to our study,

- 52 admit a complete timed gates toolkit (including a timed crossover gate) and therefore have a P-complete timed prediction problem N-TIMED-PRED,

- 99 have a planar sandpile structure and therefore do not admit a timed
crossover gate,

- 34 admit a timed crossover gate, but one is faced with an issue in the delays
when connecting the gates together,

- the 49 remaining neighborhoods (including Moore) are conjectured to do not
admit a timed crossover gate.

Remark that a crossover gate is also a timed crossover gate, hence the 12 neigh-
borhoods having a P-complete N-PRED problem are part of the 52 neighbor-
hoods having a P-complete N-TIMED-PRED problem. It is notable that 40
neighborhoods (from 7 equivalence classes) do not admit a crossover gate, but
do admit a complete timed gates toolkit allowing to prove the P-completeness
of timed prediction problem. Intuitively, following Banks approach, for these
neighborhoods the embedding of the circuit evaluation in the sandpile dynam-
ics is possible when one follows precisely the time steps, but asymptotically the
sandpile will not stay in a configuration where the result of the circuit can be
read out.

The precise characterization of the neighborhoods for which it is impossible
to follow Banks approach in proving the P-completeness of N-TIMED-PRED
is still open, and does not seem to be captured by the existence of timed crossover
gate as defined in Section 2. Proving that timed crossover gate do not exist for
von Neumann and Moore neighborhoods would reveal more obstacles to the
embedding of efficient computation within them.

**Acknowledgments.** The authors thank projects ANR-24-CE48-7504 ALARICE, HO-
RIZON-MSCA-2022-SE-01 101131549 ACANCOS, STIC AmSud CAMA 22-STIC-02.

**Disclosure of Interests.** The authors have no competing interests to declare that are relevant to the content of this article.

**References**

1. Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality: An explanation of the 1/f noise. Physical review letters **59**(4), 381 (1987)
2. Banks, E.R.: Information processing and transmission in cellular automata. Ph.D. thesis, Massachusetts Institute of Technology (1971)

3. Concha-Vega, P., Goles, E., Montealegre, P., Perrot, K.: Sandpiles prediction and crossover on $Z^2$ within moore neighborhood. Natural Computing **24**(1), 29–66 (2025), access for the reviewer: https://pageperso.lis-lab.fr/kevin.perrot/documents/crossing-moore-HAL.pdf

4. Delorme, M., Mazoyer, J.: Signals on cellular automata. In: Adamatzky, A. (ed.) Collision-based Computing, pp. 231–275. Springer-Verlag (2002)

5. Formenti, E., Perrot, K.: How Hard is it to Predict Sandpiles on Lattices? A Survey. Fundamenta Informaticae **171**, 189–219 (2019)

6. Gajardo, A., Goles, E.: Crossing information in two-dimensional sandpiles. Theoretical Computer Science **369**(1-3), 463–469 (2006)

7. Goles, E., Maldonado, D., Montealegre, P., Ollinger, N.: On the computational complexity of the freezing non-strict majority automata. In: Proceedings of AUTOMATA’2017. LNCS, vol. 10248, pp. 109–119 (2017)

8. Goles, E., Montealegre, P., Perrot, K., Theyssier, G.: On the complexity of two-dimensional signed majority cellular automata. Journal of Computer and System Sciences **91**, 1–32 (2017)

9. Goles, E., Montealegre-Barba, P., Todinca, I.: The complexity of the bootstraping percolation and other problems. Theoretical Computer Science **504**, 73–82 (2013)

10. Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Inc. (1995)

11. Jájá, J.: An introduction to parallel algorithms. Addison-Wesley (1992)

12. Moore, C., Nilsson, M.: The computational complexity of sandpiles. Journal of Statistical Physics **96**, 205–224 (1999)

13. Nguyen, V.H., Perrot, K.: Any shape can ultimately cross information on two-dimensional abelian sandpile models. In: Proceedings of AUTOMATA’2018. LNCS, vol. 10875, pp. 127–142 (2018)