论文标题
随机到达问题
The Stochastic Arrival Problem
论文作者
论文摘要
我们研究了到达问题的新修改，该修改允许除了切换节点外，还允许表现出随机和受控行为的节点。我们研究了这些扩展的计算复杂性，这是基于可及性切换游戏的现有工作的基础。特别是，我们显示出到达问题的版本，涉及仅切换和随机节点，它是\ pp {} - 很难决定其值是否大于一半，我们提供了PSPACE决策算法。
We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is \PP{}-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm.
