On the Complexity of Rolling Block and Alice Mazes
On the Complexity of Rolling Block and Alice Mazes
复制标题
论滚动块和爱丽丝迷宫的复杂性
DOI：
10.1007/978-3-642-30347-0_22
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Sebastian Jakobi
中科院分区：
文献类型：
--
作者：
M. Holzer;Sebastian Jakobi
我们研究了两个迷宫问题的计算复杂性，即滚动块和爱丽丝迷宫。简单地说，在前一个游戏中，一个人必须通过一个迷宫滚动块，在一个特定的游戏情况下结束，而在后一个，一个人必须通过一个迷宫移动速度可变的令牌按照一些规定的方向。事实证明，当块的数量或令牌的数量不受限制（无界）时，解决这样一个迷宫的问题就成为PSPACE完全的。通过从[E. D. Demaine，R. A. Hearn：A uniform framework or modeling computations as games.]的非确定性约束逻辑（NCL）的简化来展示难度。2008年，《中华人民共和国刑法典》。通过只使用大小为2×1×1的块，而不使用禁止正方形，我们改进了[K. Buchin，M. Buchin：Rolling block mazes are PSPACE-complete.J. Inform.程序、2012年，在最好的滚动块迷宫。此外，我们还考虑这些迷宫游戏的有界变体，即，当块或令牌的数量由一个常数限制时，并证明了与图的可达性问题的变体的密切关系。
We investigate the computational complexity of two maze problems, namely rolling block and Alice mazes. Simply speaking, in the former game one has to roll blocks through a maze, ending in a particular game situation, and in the latter one, one has to move tokens of variable speed through a maze following some prescribed directions. It turns out that when the number of blocks or the number of tokens is not restricted (unbounded), then the problem of solving such a maze becomes PSPACE-complete. Hardness is shownviaa reduction from the nondeterministic constraint logic (NCL) of [E. D. Demaine,R. A. Hearn: A uniform framework or modeling computations as games. Proc.CCC, 2008] to the problems in question. By using only blocks of size 2×1×1, and no forbidden squares, we improve a previous result of [K. Buchin,M. Buchin: Rolling block mazes are PSPACE-complete.J. Inform. Proc., 2012] on rolling block mazes to best possible. Moreover, we also consider bounded variants of these maze games, i.e., when the number of blocks or tokens is bounded by a constant, and prove close relations to variants of graph reachability problems.