ARRIVAL: A zero-player graph game in NP ∩ coNP
Prof. Dr. Bernd Gärtner
ETH Zürich, Schweiz
Time & Place
The presentation on May 30, 2017 will be given in the Lukasklause (Schleinufer 1, 39104 Magdeburg) and starts at 5.00 p.m. (Historischer Raum).
Abstract
Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a special nature: every time the train traverses a switch, the switch will change its position immediately afterwards. Hence, the next time the train traverses the same switch, the other direction will be taken, so that directions alternate with each traversal of the switch.
Given a network with origin and destination, what is the complexity of deciding whether the train, starting at the origin, will eventually reach the destination?
It is easy to see that this problem can be solved in exponential time, but we are not aware of any polynomial-time method. In this talk, I explain where the problem comes from and prove that is is in NP ∩ coNP; actually in UP ∩ coUP (problems with unique NP/coNP certificates).
This raises the question whether people have so far just failed to find a (simple) polynomial-time solution, or whether the complexity status is more subtle, as for some other well-known (two-player) graph games.
Joint work with Jérôme Dohrau, Hagar Mosaad, Manuel Kohler, Jiří Matoušek, Emo Welzl