  Chip-firing and rotor-routing are two well-studied examples of abelian
networks. We study the complexity of their respective reachability problems. We
show that the rotor-routing reachability problem is decidable in polynomial
time, and we give a simple characterization of when a chip-and-rotor
configuration is reachable from another one. For chip-firing, it has been known
that the reachability problem is in P if we have a class of graphs whose period
length is polynomial (for example, Eulerian digraphs). Here we show that in the
general case, chip-firing reachability is hard in the sense that if the
chip-firing reachability problem were in P for general digraphs, then the
polynomial hierarchy would collapse to NP. We encode graphs by their adjacency
matrix, and we encode ribbon structures "succinctly", only remembering the
number of consecutive parallel edges.
