Rotor-routing halting problem

From Egres Open
Jump to: navigation, search


The rotor-routing halting problem asks the following: Given an initial chip-and-rotor configuration on a digraph, does the rotor-routing game eventually terminate?

A more refined version of the problem is the halting configuration problem: If the rotor-routing game terminates, what is the final configuration?


Remarks

  • Even though the complexity of the rotor-routing halting problem is open, it is a trivial problem in many special cases: For example, if the chip-configuration is nonnegative with at least one chip, and the digraph is strongly connected, then the rotor-routing game does not terminate. If here is a sink vertex that is reachable on a directed path from each other vertex, then the rotor-routing game always terminates.