ARRIVAL: Next Stop in CLS.

We study the computational complexity of ARRIVAL, a zero-player game on$n$-vertex switch graphs introduced by Dohrau, G\"{a}rtner, Kohler,Matou\v{s}ek, and Welzl. They showed that the problem of deciding terminationof this game is contained in $\text{NP} \cap \text{coNP}$. Karthik C. S.recently introduced a search variant of ARRIVAL and showed that it is in thecomplexity class PLS. In this work, we significantly improve the known upperbounds for both the decision and the search variants of ARRIVAL.

First, we resolve a question suggested by Dohrau et al. and show that thedecision variant of ARRIVAL is in $\text{UP} \cap \text{coUP}$. Second, weprove that the search variant of ARRIVAL is contained in CLS. Third, we give arandomized $\mathcal{O}(1.4143^n)$-time algorithm to solve both variants.

Our main technical contributions are (a) an efficiently verifiablecharacterization of the unique witness for termination of the ARRIVAL game, and(b) an efficient way of sampling from the state space of the game. We show thatthe problem of finding the unique witness is contained in CLS, whereas it waspreviously conjectured to be FPSPACE-complete. The efficient sampling procedureyields the first algorithm for the problem that has expected runtime$\mathcal{O}(c^n)$ with $c<2$.