The Non-Deterministic Constraint Logic and Its Applications in Computational Complexity
孜文 刘 · Computer Science and Application · 2017
过去几十年，有许多组合谜题的计算复杂度被确定了。本文介绍了非确定性限制逻辑，并用归约为非确定性限制逻辑的方法，证明了一种类似于推箱子的种豆游戏的计算复杂度为多项式空间完全的。 The computational complexity of several combinatorial puzzles has been determined in the liter-ature in the past few decades. We introduce the non-deterministic constraint logic (NCL) in this paper. As an application, we prove that Beanstalk, a Sokoban-like puzzle, is PSPACE-complete by reduction from NCL.