The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications
The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications
复制标题
计算的非确定性约束逻辑模型：归约和应用
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
E. Demaine
中科院分区：
文献类型：
--
作者：
R. Hearn;E. Demaine
我们提出了一种基于在顶点上具有最小流入约束的加权有向图中反转边缘方向的非确定性计算模型。通过量化布尔公式的简化，决定是否可以操纵这个简单的图模型来反转特定边的方向，这被证明是 PSPACE 完全的。我们在各种特殊情况下证明了这个结果，包括平面图和高度受限的顶点配置，其中一些对应于一种被动约束逻辑。我们的框架受到 Flake 和 Baum [2] 开发的“广义高峰逻辑”的启发（实际上是其概括）。我们通过简单的简化来说明我们的计算模型的重要性，以表明多个运动规划问题是 PSPACE 困难的。我们沿着这些思路的主要结果是，经典的无限制滑块谜题是 PSPACE 困难的，即使棋子被限制为所有多米诺骨牌（1×2 块）并且目标只是移动特定棋子。之前不知道这些谜题的复杂性结果。这一结果可以看作是对现有结果的强化，即限制高峰时段？谜题是 PSPACE 完备的 [2]，我们也给出了一个更简单的证明。最后，我们通过证明推块谜题 Sokoban 是 PSPACE 完全的 [1] 的现有结果，证明即使不允许任何障碍，它也是 PSPACE 完全的。
We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restrictedv ertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the "Generalized Rush Hour Logic" developed by Flake and Baum [2].We illustrate the importance of our model of computation by giving simple reductions to show that multiple motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restrictedto be all dominoes (1×2 blocks) andthe goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour? puzzles are PSPACE-complete [2], of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [1], by showing that it is PSPACE-complete even if no barriers are allowed.