《花之谜题》的计算复杂度

 

作者:杨超

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

“P是否等于NP?”是Clay数学研究所(Clay Mathematics Institute,缩写CMI)2000年评出的七个奖金100万美元公开数学问题中的一个。Clay数学研究所的官网对每个问题都有正式的描述,其中对“P=NP?”问题的描述中,以扫雷游戏作为NP完全问题的代表,作了一些深入浅出的介绍,见下面官网截图。可见,一些益智小游戏和被数学家认为最重要的数学问题也有密切联系。

由于长期对推箱子游戏的喜爱,从而对推箱子类游戏的计算复杂度也很感兴趣。一般有点意思的推箱子类游戏对应的判定问题的计算复杂度,大多是NP完全或PSPACE完全的。对于具体一个推箱子类游戏,要完全确定其计算复杂度,有时也不见得容易。其中涉及的一个特别的因素是游戏的答案长度:是否总有多项式长度的答案?还是存在例子使得答案长度达到指数级别?

《花之谜题》(Hanano Puzzle)是一个令人爱不释手的游戏,我之前有两篇博文都分别介绍过。这个游戏特别之处在于一方面具有引力,另一方面可以通过开花抵抗引力向上推。

最近,我和合作者在 Elsevier 出版集团旗下的学术期刊 Information Processing Letters 上发表了一篇文章,研究了这个游戏的计算复杂度。有兴趣的朋友可以在此下载该文章的被接收的手稿:

Hanano Puzzle is NP-hard

正式发表的版本可以在 Elsevier 官网下载:

https://authors.elsevier.com/a/1YRTa4ZKAYBpN(此链接于2019年3月13日前都可以免费下载)正式版本的排版更为赏心悦目一些,学术出版集团 Elsevier 还是在学术出版过程中创造了不少价值。

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