  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.
