# A simple lower bound for ARRIVAL

Graham Manuell  Centre for Mathematics, University of Coimbra, Coimbra,
Portugal<EMAIL_ADDRESS>
(Date: August 2021)

###### Abstract.

The Arrival problem introduced by Dohrau, Gärtner, Kohler, Matoušek and Welzl
concerns a train moving on a directed graph proceeding along outward edges
according to the position of ‘switches’ at each vertex, which in turn are
toggled whenever the train passes through them. The problem asks whether the
train every reaches a designated destination vertex. It is known that Arrival
is contained in $\mathsf{UP}\cap\mathsf{coUP}$, while the previously best
published lower bound is that it is $\mathsf{NL}$-hard. In this note we
provide a simple reduction to the $\textsc{Digicomp}_{\mathsf{EXP}}$ problem
considered by Aaronson. It follows in particular that Arrival is both
$\mathsf{CC}$-hard and $\mathsf{PL}$-hard.

###### Key words and phrases:

switching game, reachability, pseudorandom walk, complexity class, comparator
circuit

The author acknowledges financial support from the Centre for Mathematics of
the University of Coimbra (UIDB/00324/2020, funded by the Portuguese
Government through FCT/MCTES)

##  1\. Introduction

A _switch graph_ consists of a set of vertices $V$ and two endomorphisms
$s_{0},s_{1}\colon V\to V$ and can be thought of as a directed graph with
directed edges from each $v$ to $s_{0}(v)$ and from $v$ to $s_{1}(v)$. Given a
switch graph $G=(V,s_{0},s_{1})$, we imagine a train starting a some vertex
$s$ and traversing the graph is the following way. Each vertex of the graph
contains a switch initialised to state $0$. At each time step, if the train is
at a vertex $v$ and the switch at $v$ is in state $i\in\\{0,1\\}$, the train
moves from a vertex $v$ to $s_{i}(v)$ and the state of the switch at $v$ is
toggled. The Arrival problem [3] asks whether the train every reaches a
specified destination vertex $t$.

It is shown in [3] that Arrival is in $\mathsf{NP}\cap\mathsf{coNP}$ and this
is improved to $\mathsf{UP}\cap\mathsf{coUP}$ in [5]. Recently, an algorithm
has been given that solves it in $2^{\mathcal{O}(\sqrt{n}\log{n})}$ time [6].
On the other hand, the only published lower bound is given in [4] (for a
formally slightly more general game) where $\mathsf{NL}$-hardness is proved.

However, in [1] Aaronson studies a highly related problem. The Digi-Comp II
was a mechanical toy computer where small balls rolls down an incline and are
deflected by toggles that divert their path, which conversely causes the
toggles to be kicked back into a different setting. The effect is that the
balls behave exactly the train in Arrival with the graph $G$ restricted to be
acyclic.

Explicitly, let us define a switch graph to be _acyclic_ if there are no
cycles in the corresponding directed graph aside from self-loops. Then the
Digicomp problem asks for an acyclic switch graph $G=(V,s_{0},s_{1})$, a
starting vertex $s$, a destination vertex $t$ and a number of balls $T$
encoded in unary, whether after $T$ balls are released sequentially from $s$
any ever reach $t$. (Technically, to match the original definition there are
should some further restrictions, such as $s_{0}(t)=s_{1}(t)=t$, but our
version is easily seen to be equivalent.) Aaronson shows that this problem is
in fact $\mathsf{CC}$-complete.

Recall that $\mathsf{CC}$ is the class of problems which are log-space
reducible to the evaluation of a circuit built about of comparator gates
(which send $(x,y)$ to $(x\wedge y,x\vee y)$) without implicit fan-out (see
[7, 2]). It is known that $\mathsf{CC}$ contains $\mathsf{NL}$.

We note it is not completely immediate that Arrival is $\mathsf{CC}$-hard:
while the Digicomp problem is almost Arrival restricted to acyclic graphs,
this is not quite true, since unlike Arrival, Digicomp involves ‘multiple
trains’. Nonetheless, it is still true that Digicomp can be reduced Arrival as
we show below.

In fact, we can say say more. The problem $\textsc{Digicomp}_{\mathsf{EXP}}$
is defined in [1] in the same way as Digicomp except the number of balls $T$
is encoded in _binary_ — that is, the number of balls used can be exponential
in the input size. This problem is still in $\mathsf{P}$, but it might be
strictly harder than Digicomp. We will show that
$\textsc{Digicomp}_{\mathsf{EXP}}$ can be reduced Arrival in logarithmic
space. Consequently, Arrival is both $\mathsf{CC}$-hard and
$\mathsf{PL}$-hard.

I do not claim any particular novelty here; every nontrivial piece of the
argument used to derive this result is already known to others. However, they
do not been appear to have been put together explicitly before and all the
literature on Arrival only mentions the $\mathsf{NL}$-hardness result. The aim
of this paper is to make the stronger lower bounds more widely known.

##  2\. Results

As noted in the original paper [3], it is not difficult to construct switch
graphs which act as binary counters. A 4-bit counter is given in the following
diagram, where solid lines represent the $s_{0}$ edges and dashed lines
represent the $s_{1}$ edges.

$C$$B$$A$

This can be used to pass down the path at $A$ 16 times and then the path at
$B$ once (before possibly repeating the whole sequence over again). Here we
have omitted the full path starting at $A$, which would of course need to
eventually loop back to the starting vertex of the counter at $C$.

In general, given some counter similar to that above that counts to $T$, we
can make $B$ connect back to $C$ via a solid line and to a new final state
$B^{\prime}$ via a dotted line. This will cause the counter to run twice
before reaching $B^{\prime}$ and hence we obtain a counter that counts to
$2T$.

On the other hand, if we connect $B$ to $A$ instead of looping directly back
to $C$, we will end up visiting $A$ one additional time before starting the
counter again. Thus, the new counter will count up to $2T+1$.

Now by repeatedly applying these two techniques, we can build a counter to
count to any number based on its binary expansion. For instance, the following
counter visits $A$ $22=10110_{2}$ times before reaching $B$.

$C$$B$$A$

These counters only require $\lfloor\log T\rfloor+1$ nodes to count up to $T$.
We now arrive at the following result, where we use a counter to run through
an acyclic graph multiple times and hence simulate multiple trains.

######  Proposition 2.1.

${\textsc{Digicomp}}_{\mathsf{EXP}}$ is a $\mathsf{AC}^{0}$-reducible to
Arrival.

Consider the $\textsc{Digicomp}_{\mathsf{EXP}}$ problem for an acyclic switch
graph $G$, starting vertex $s$, destination vertex $t$ and a number of balls
$T$. We construct a counter up to $T$ as described above where the output $A$
connects to the graph $G$ at the vertex $s$ and the output at $B$ is a new
vertex $F$ with $s_{0}(F)=s_{1}(F)=F$. The ‘leaf’ vertices of $G$ (i.e. those
vertices $v$ such that $s_{0}(v)=s_{1}(v)=v$) have their outputs modified so
that they connect back to the counter at $C$. The new starting vertex is $C$
and the new destination vertex is still $t$.

######  Remark 2.2.

We have seen it is easy to repeat an operation exponentially many times in
Arrival and then do something else. This might make us hope that we can
simulate the succinct 0-player reachability switching game of [4], which was
shown there to be $\mathsf{P}$-hard. However, no simple modification of our
approach is able to achieve this.

The problem is that to simulate Boolean circuits as in [4] it is necessary to
put the entire program in a big loop as we have done here and have the train
pass through the circuit multiple times in order to feed the inputs into the
circuit. However, then if we ever use a counter to make the train go down one
path $2^{n}$ times before going along another path, by the time we reach the
counter again it will have been reset to its initial position and the train
will go down the first path yet again instead of starting to repeat the second
path.

We could try to avoid this by making sure the second path never loops back to
this counter again, but this is not compatible with the global loop. We also
note that it _is_ , of course, possible to alternate between paths $A$ and $B$
so that in the end both have been traversed $2^{n}$ times, but now it is not
clear how to make logic gates work.

Finally, we note in passing that it is possible to simulate the non-succinct
0-player reachability switching game by encoding each node of high out-degree
using a binary tree, but this takes exponentially many nodes and so is not
helpful for the succinct version. $\triangle$ △

Since $\textsc{Digicomp}_{\mathsf{EXP}}$ is clearly harder than Digicomp,
which is $\mathsf{CC}$-complete, it now follows that Arrival is
$\mathsf{CC}$-hard. The precise difficulty of
$\textsc{Digicomp}_{\mathsf{EXP}}$ is not known, but in a comment at [1] Itai
Bar-Natan proves that $\textsc{Digicomp}_{\mathsf{EXP}}$ is
$\mathsf{PL}$-hard. Thus, Arrival is $\mathsf{PL}$-hard too. We reproduce the
argument here for completeness.

######  Proposition 2.3.

${\textsc{Digicomp}}_{\mathsf{EXP}}$ is $\mathsf{PL}$-hard.

The problem of determining if there are at least $k$ paths from $s$ to $t$ in
an directed acyclic graph $G$ is $\mathsf{PL}$-complete. By recursively
splitting the vertices in the graph we may assume the out-degree of each
vertex is at most 2 without loss of generality.

We can now define a new graph $G^{\prime}$ to have a vertex $(v,i)$ for each
$v\in G$ and $i\in\\{0,\dots,n-1\\}$, where $n$ is the number of vertices in
$G$, and an edge from $(u,i)$ to $(v,i+1)$ whenever $u\neq t$ and there is an
edge from $u$ to $v$ in $G$ and also when $u=v=t$. Note that the number of
paths from $(s,0)$ to $(t,n-1)$ in $G^{\prime}$ is then precisely equal to the
number of paths from $s$ to $t$ in $G$. Moreover, out-degrees of vertices in
$G^{\prime}$ are also at most $2$. This construction can be done in
logarithmic space.

Finally, we construct a switch graph from $G^{\prime}$ by arbitrarily choosing
one of the edges out of each vertex to be the $s_{0}$ edge and the other to be
the $s_{1}$ in the case the out degree is 2. When the degree is less than 2 we
make the remaining edges out of $v$ point to a new vertex $F$ which satisfies
$s_{0}(F)=s_{1}(F)=F$. The vertex $(t,n-1)$ is a special case, which we
discuss later. It is not hard to see that if we start $2^{n}$ balls at $(s,0)$
then the number of balls that reach the vertex $(v,i)$ is equal to
$2^{n-i}c(v,i)$ where $c(v,i)$ is the number of paths from $(s,0)$ to $(v,i)$
in $G^{\prime}$. Thus, $c(t,n-1)$ balls arrive at $(t,n-1)$, which is also
equal to the number of paths from $s$ to $t$ in $G$.

Finally, we connect $(t,n-1)$ to a counter that sends the first $k-1$ balls to
$F$ and the remaining balls to a new destination vertex $D$. This counter is
the Digicomp analogue of the counter for Arrival we described above. The
difference is that whenever we would have looped back to the start of the
counter we instead just connect the vertex to itself. (When this counter is
interpreted in Arrival the counter will connect then back to the start of
vertex $(s,0)$.) A ball will now arrive at $D$ precisely if there are at least
$k$ paths from $s$ to $t$ in $G$, as required. Finally, note that the
construction of the switch graph can be done in logarithmic space and so we
are done.

It is also notable that at the end of the simulation of the switch graph
above, the position of the switch at $(t,n-1)$ contains the answer to whether
the number of paths from $s$ to $t$ is odd or even, which is a
${\oplus}\mathsf{L}$-complete problem. So if we could use this to influence
the location of a ball somehow (i.e. to cause a later ball to fall into a
position no ball would have reached before), this would show that Arrival is
${\oplus}\mathsf{L}$-hard. However, there does not appear to be any obvious
way to do this.

## References

  * [1] S. Aaronson.  The power of the Digi-Comp II, 2014.  https://www.scottaaronson.com/blog/?p=1902.
  * [2] S. A. Cook, Y. Filmus, and D. T. M. Lê.  The complexity of the comparator circuit value problem.  arXiv preprint arXiv:arXiv:1208.2721, 2013.
  * [3] J. Dohrau, B. Gärtner, M. Kohler, J. Matoušek, and E. Welzl.  ARRIVAL: A zero-player graph game in NP $\cap$ coNP.  In M. Loebl, J. Nešetřil, and R. Thomas, editors, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pages 367–374. Springer, 2017.
  * [4] J. Fearnley, M. Gairing, M. Mnich, and R. Savani.  Reachability switching games.  Logical Methods in Computer Science, 17(2):10:1–10:29, 2021.
  * [5] B. Gärtner, T. D. Hansen, P. Hubáček, K. Král, H. Mosaad, and V. Slívová.  ARRIVAL: Next stop in CLS.  arXiv preprint arXiv:arXiv:1802.07702, 2018.
  * [6] B. Gärtner and H. H. P. Haslebacher, Sebastian.  A subexponential algorithm for ARRIVAL.  arXiv preprint arXiv:2102.06427, 2021.
  * [7] E. W. Mayr and A. Subramanian.  The complexity of circuit value and network stability.  Journal of Computer and System Sciences, 44(2):302–323, 1992.