On The Complexity of Counter Reachability Games

Counter reachability games are played by two players on a graph with labelled edges. Each move consists of picking an edge from the current location and adding its label to a counter vector. The objective is to reach a given counter value in a given location. We distinguish three semantics for counter reachability games, according to what happens when a counter value would become negative: the edge is either disabled, or enabled but the counter value becomes zero, or enabled. We consider the problem of determining the winner in counter reachability games and show that, in most cases, it has the same complexity under all semantics. This constrasts with the one-player case, for which the decision problem is decidable without any elementary upper bound under the first semantics, whereas it is NP-complete under the third one. Surprisingly, under one semantics, the complexity in dimension one depends on whether the objective value is zero or any other integer.