论文标题
即使没有楼梯，穿过门也很难：通过门配件证明pspace-hardness
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
论文作者
论文摘要
一个门小工具具有两个状态和三个隧道，可以由代理商（玩家，机器人等）穿越：“开放”和“闭合”隧道将小工具的状态分别设置为开放和关闭，而当门处于开放状态时，“遍历”隧道可以穿越。我们证明，决定代理是否可以通过这样的门品的平面组装来确定代理商是否可以从一个位置转移到另一个位置，从而消除了传统的跨界小工具需求，从而简化了过去的Pspace-Hardness lemmmings和Nintendo Games Games Mario Bros.，Zelda和Donkey Kong kong and Donkey Kong country的Pspace-Hardness证明。我们的结果除了在门小工具中嵌入开口，闭合和横穿隧道的当地平面之一外，所有结果都包含了所有。在剩下的情况下，我们证明了np-hardness。 我们还介绍和分析了一种更简单的门小工具，称为自闭门。这个小工具有两个州和两个隧道，类似于门的“开放”和“横纵向”的隧道，除了穿越遍及横梁的隧道还关闭了门。在一个称为对称自关闭门的变体中，只有关闭门时，才能穿越“打开”隧道。我们证明，决定代理是否可以通过两种类型的自关闭门的平面组件从一个位置移动到另一个位置是PSPACE的完整。然后，我们将此框架应用于八种不同的3D Mario Games和Sokobond的新PSPACE-HARDNESS结果。
A door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "open" and "close" tunnel sets the gadget's state to open and closed, respectively, while the "traverse" tunnel can be traversed if and only if the door is in the open state. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of such door gadgets, removing the traditional need for crossover gadgets and thereby simplifying past PSPACE-hardness proofs of Lemmings and Nintendo games Super Mario Bros., Legend of Zelda, and Donkey Kong Country. Our result holds in all but one of the possible local planar embedding of the open, close, and traverse tunnels within a door gadget; in the one remaining case, we prove NP-hardness. We also introduce and analyze a simpler type of door gadget, called the self-closing door. This gadget has two states and only two tunnels, similar to the "open" and "traverse" tunnels of doors, except that traversing the traverse tunnel also closes the door. In a variant called the symmetric self-closing door, the "open" tunnel can be traversed if and only if the door is closed. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of either type of self-closing door. Then we apply this framework to prove new PSPACE-hardness results for eight different 3D Mario games and Sokobond.
