摘要
过去几十年,有许多组合谜题的计算复杂度被确定了。本文介绍了非确定性限制逻辑,并用归约为非确定性限制逻辑的方法,证明了一种类似于推箱子的种豆游戏的计算复杂度为多项式空间完全的。
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.
出处
《计算机科学与应用》
2017年第5期407-413,共7页
Computer Science and Application
基金
国家自然科学基金青年科学基金项目(11201496),广东省自然科学基金(2015A030313222)。
