论文标题
反抗重力：哈纳诺难题的复杂性
Defying Gravity: The Complexity of the Hanano Puzzle
论文作者
论文摘要
使用可见性表示的概念，我们的论文建立了非确定性约束逻辑（NCL）问题的新属性（一个非常方便的问题，可以证明具有推动块的可逆游戏的PSPACE硬度非常方便）。直接使用此属性会引入显示Pspace硬度所需的小工具数量的爆炸，但是我们展示了如何将该数字从32下降到只有三个，而在特定情况下则降到两个！我们将其作为迈向更广泛，更一般的框架来研究具有不可逆转的重力的游戏的一步，并使用此连接指导间接多项式时间从NCL问题到Hanano拼图（这是NP-HARD） - 实际上是PSPACE完整的。
Using the notion of visibility representations, our paper establishes a new property of instances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete problem that is very convenient to prove the PSPACE-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show PSPACE-hardness, but we show how to bring that number from 32 down to only three in general, and down to two in a specific case! We propose it as a step towards a broader and more general framework for studying games with irreversible gravity, and use this connection to guide an indirect polynomial-time many-one reduction from the NCL problem to the Hanano Puzzle -- which is NP-hard -- to prove it is in fact PSPACE-complete.
