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.
翻译：我们研究对抵达问题的新修改,除了转换节点外,还允许显示随机和受控制行为的节点。我们研究这些扩展的计算复杂性,以关于可达性转换运动会的现有工作为基础。特别是,我们展示抵达问题的不同版本,涉及仅仅切换和随机节点,很难决定它们的价值是否超过一半,我们给出了PSPACE决定算法。
相关内容
CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点，具有清晰的数学轮廓和严格的数学格式。官网链接：https://link.springer.com/journal/37
Arxiv
0+阅读 · 2023年1月22日
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员