论文标题
可逆确定性系统的Pspace完整性
PSPACE-Completeness of Reversible Deterministic Systems
论文作者
论文摘要
我们证明了几种可逆的，完全确定性的系统的PSPACE完整性。从核心上讲，我们为此类证明开发了一个框架（基于Tsukiji和Hagiwara的结果，以及通过小工具进行运动计划的框架），表明任何可以实现三个基本小工具的系统都是Pspace-Complete。然后，我们将此框架应用于四个不同的系统，显示其多功能性。首先，我们证明确定性的约束逻辑是PSPACE完整的，在2008年以前的参数中解决了错误。其次，我们为弗雷德金（Fredkin）和toffoli的可逆“台球球”模型和40年前的Toffoli模型提供了新的Pspace-Hardness证明，从40年前开始，只有两个球一次移动，就可以新地确定硬度。第三，我们证明了零播放器运动计划的PSPACE完整性，并具有任何可逆的确定性相互作用$ K $ -Tunnel小工具和“旋转顺时针旋转”小工具（分支走廊的零游戏类似物）。第四，我们提供了更简单的证据，表明零播放器的运动计划仅是一个小工具，即3旋转器。这些结果反过来应该使证明其他可逆的确定性系统的pspace固定性变得更加容易。
We prove PSPACE-completeness of several reversible, fully deterministic systems. At the core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara and a framework for motion planning through gadgets), showing that any system that can implement three basic gadgets is PSPACE-complete. We then apply this framework to four different systems, showing its versatility. First, we prove that Deterministic Constraint Logic is PSPACE-complete, fixing an error in a previous argument from 2008. Second, we give a new PSPACE-hardness proof for the reversible `billiard ball' model of Fredkin and Toffoli from 40 years ago, newly establishing hardness when only two balls move at once. Third, we prove PSPACE-completeness of zero-player motion planning with any reversible deterministic interacting $k$-tunnel gadget and a `rotate clockwise' gadget (a zero-player analog of branching hallways). Fourth, we give simpler proofs that zero-player motion planning is PSPACE-complete with just a single gadget, the 3-spinner. These results should in turn make it even easier to prove PSPACE-hardness of other reversible deterministic systems.
