非确定性限制逻辑及其在计算复杂度中的应用
The Non-Deterministic Constraint Logic and Its Applications in Computational Complexity
DOI: 10.12677/CSA.2017.75049, PDF, HTML, XML, 下载: 1,428  浏览: 1,834  国家自然科学基金支持
作者: 刘孜文：华南理工大学软件学院，广东 广州；杨 超*：中山大学数学学院，广东 广州
关键词: 非确定性限制逻辑；计算复杂度；组合谜题；Non-Deterministic Constraint Logic； Computational Complexity； Combinatorial Puzzles
摘要: 过去几十年，有许多组合谜题的计算复杂度被确定了。本文介绍了非确定性限制逻辑，并用归约为非确定性限制逻辑的方法，证明了一种类似于推箱子的种豆游戏的计算复杂度为多项式空间完全的。
Abstract: 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.
文章引用：刘孜文, 杨超. 非确定性限制逻辑及其在计算复杂度中的应用[J]. 计算机科学与应用, 2017, 7(5): 407-413. https://doi.org/10.12677/CSA.2017.75049

参考文献

[1] Culberson, J.C. (1997) Sokoban is PSPACE-Complete. Technical Report TR 97-02, Department of Computing Science, University of Alberta, Edmonton.
[2] Hearn, R.A. and Demaine, E.D. (2005) PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation. Theoretical Computer Science, 343, 72-96.
https://doi.org/10.1016/j.tcs.2005.05.008
[3] He, W., Liu, Z. and Yang, C. (2017) Snowman is Pspace-Complete. Theoretical Computer Science, 677, 31-40.
https://doi.org/10.1016/j.tcs.2017.03.011
[4] Pereira, A.G., Ritt, M. and Buriol, L.S. (2016) Pull and Push Pull Are PSPACE-Complete. Theoretical Computer Science, 628, 50-61.
https://doi.org/10.1016/j.tcs.2016.03.012
[5] Solovey, K. and Halperin, D. (2016) On the Hardness of Unlabeled Multi-Robot Motino Planning. The International Journal of Robotics Research, 35, 1750-1759.
https://doi.org/10.1177/0278364916672311
[6] Flake, G.W. and Baum, E.B. (2002) Rush Hour is Pspace-complete, or Why You Should Generously Tip Parking Lot Attendants. Theoretical Computer Science, 270, 895-911.
https://doi.org/10.1016/S0304-3975(01)00173-6
[7] Buchin, K. and Buchin, M. (2012) Rolling Block Mazes Are PSPACE-Complete. Journal of Information Processing, 20, 719-722.
https://doi.org/10.2197/ipsjjip.20.719
[8] Van der Zanden, T.C. and Bodlaender, H.L. (2015) Pspace-Completeness of Bloxorz and of Games with 2-Buttons. In: Paschos, V.T.H. and Widmayer, P., Eds., Algorithm and Complexity, Springer, Berlin, 403-415.
https://doi.org/10.1007/978-3-319-18173-8_30
[9] Braingle (2017) Beanstalk Puzzle Game.
http://www.braingle.com/games/beans/index.php?play=1