《堆雪人推箱子》是PSPACE完全的

 

作者:杨超

本文地址:http://sokoban.ws/blog/?p=3444

去年2月份,我写了一篇博文介绍了推箱子游戏(Sokoban)的计算复杂度是PSPACE完全的。同年4月份,我又写了一篇博文介绍了一个推箱子变种游戏《堆雪人推箱子(A good snowman is hard to build)》

写了这两篇博文后,我产生了一个想法,证明堆雪人推箱子(简称Snowman)的计算复杂度也是PSPACE完全的。经过一番努力,我把这个想法写成了一篇论文,投到由荷兰的学术出版集团Elsevier发行的期刊《Theoretical Computer Science》。该论文有三名共同作者,我是通讯作者(corresponding author)。今年(2017年)3月,被正式接收了,并于3月18日在网上发表了。

该论文永久有效的DOI地址:http://dx.doi.org/10.1016/j.tcs.2017.03.011

根据和出版社之间的通常的版权协议,我有权在个人博客分享被接收的手稿(accepted manuscript),但经过重新排版的正式发表的期刊论文(published journal article)的版权归Elsevier出版集团。本篇博文的目的就是提供该论文手稿的下载。

手稿下载:snowman_is_pspace_complete.pdf

就在论文被接受前后,我在位于上海复旦大学校内的上海数学中心举办的一次小型的图论青年学者研讨会(Graph Young Theorists Workshop)上,对这个问题作了一个20分钟报告。My presentation slides for this workshop can be also downloaded from here.

文章被接收的时间恰逢MF8推箱子比赛马上第八周年了,而且只差几期就是第100期的比赛了。又关注推箱子已近二十年了,能发表一篇与推箱子相关的学术论文,我十分高兴。

我早在1999年上大学时通过互联网搜索,看到加拿大阿尔伯特大学的Joseph C. Culberson证明推箱子是PSPACE完全问题的文章。但是那时文章中出现的PSPACE和Turing Machine(图灵机)等术语对我如同天书。

2003年读研究生后,有一学期学习了计算复杂度的课程,以Garey和Johnson合著 Computers and Intractability: A Guide to the Theory of NP-Completeness为教材。但此书讨论NP完全问题为主,学了以后,对PSPACE完全还是一头雾水。

2007年工作后,断断续续讲授了《离散数学》课程若干次。备课时查阅资料,对形式语言、可计算理论、计算复杂度理论有了进一步的了解。

2016年春节,因在乡下过年,上网和使用计算机不方便。于是利用安卓智能手机反复阅读了关于推箱子计算复杂度的几篇论文,终于第一次搞明白了。

2016年4月有了撰写关于推箱子变种Snowman复杂度论文的想法。8月开始动笔,10月发现一个严重的漏洞,关键部分重写。

11月11日投稿到Theoretical Computer Science期刊。

2017年1月30日,大年初三,收到审稿意见,需要小幅度修改。节后经过近一周的反复修改,我2月16日提交了修改稿。到了3月14日,文章被主编接收,转入出版流程。

3月17日深夜,我在线填了关于版权、插图颜色、抽印本等几个表格后,3月18日,文章就以接收文稿(accepted manuscript)的形式在线了,论文的DOI也正式生效了。由于我在Elsevier的投稿系统中绑定了ORCID,3月19日,这篇文章就马上被Crossref自动加入到我的ORCID作品列表里去了。

3月23日,文章经过编辑重新排版的校样稿也出来了,排版编辑工作非常细致,改正了我好几处单词拼写错误。提供SkyLaTeX或传统的PDF文件注释两种方法给作者做最后的校对。我采取SkyLaTeX在线方式完成的样稿的校对工作,并回复了surveymonkey上对这种在线校对方式的一个调查问卷。

3月28日,校对过的样稿(corrected proof)也上线了,替代了原来的接收文稿(accepted manuscript)。

5月3日,文章分配了卷号、期号和页码,正式发表了。同时提供50天的免费下载:

https://authors.elsevier.com/a/1U~4b15DaHuwaY

推箱子的PSPACE完全性算不上什么特别深奥的学问,但从1999年到2017年,也耗费了我将近18年时断时续的追寻,才彻彻底底搞明白了。

此条目发表在 推箱子, 数学, 游戏, 计算机 分类目录。将固定链接加入收藏夹。