A zero-player graph game in NP $cap$ coNP
A zero-player graph game in NP $cap$ coNP
复制标题
NP $cap$ coNP 中的零玩家图游戏
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
E. Welzl
中科院分区：
文献类型：
--
作者：
Jérôme Dohrau;Bernd Gärtner;Manuel Kohler;Jirí Matousek;E. Welzl
假设火车沿着铁路网络从指定的起源开始，目的是到达指定的目的地。但是，网络具有特殊的性质：每次火车遍历开关时，开关都会立即更改其位置。因此，下次火车穿越相同的开关时，将采取另一个方向，以便方向与开关的每个遍历交替。给定一个具有原点和目的地的网络，决定从原点开始的火车最终会到达目的地的复杂性是什么？很容易看到这个问题可以在指数时间内解决，但是我们不知道任何多项式时间方法。在这篇简短的论文中，我们证明了问题在NP $ CAP $ CONP中。这就提出了一个问题，我们是否刚刚找不到（简单）多项式时间解决方案，还是复杂性状态是否更微妙，对于其他一些知名（两人）的图形游戏。
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 short paper, we prove that the problem is in NP $cap$ coNP. This raises the question whether we have 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.