常有一种烦恼在心头的文章（处处是NP问题的人生）
常有一种烦恼在心头的文章（处处是NP问题的人生）PS：如果你喜欢这个系列的漫画，欢迎关注公众号TILcomic~对三消游戏来说，输入规模即是给定盘面的大小，而主要问题则是如何在限定步数内使某个特定位置上的宝石消失。研究者们为各种逻辑门的组件构造了等价的宝石排列，并证明了在盘面足够大的情况下可以将任何3SAT问题（SAT的一种变形）的逻辑电路转化成对应的三消盘面。事实上，不光是三消游戏，包括超级马里奥和宠物小精灵在内的一些经典任天堂游戏也被证明拥有NP完全的复杂度。如果三消最后真的成为了P=NP的突破口，对游戏玩家来说会是个有趣的场景吧。想想看，游戏党对买买买爱好者们说“你知道么，三消游戏和买哪些东西凑单最划算是一类的问题哦~”大概可以解决很多人生矛盾吧。cite:arxiv/pdf/1403.5830.pdf
2014年的一篇论文指出，三消游戏具有NP完全的复杂性。这个结论把大家喜闻乐见的休闲游戏和计算复杂性理论中最重要的一个概念联系了起来。
计算复杂性理论所考虑的是一个问题的输入规模和算法的执行时间之间的关系。一般认为如果执行时间不超过输入规模n的某个多项式函数，就是实用性较高的算法。存在这种算法的问题被称为多项式复杂度的问题，取Polynomial的首字母P作为代表。例如，对n个数字进行排序，使用冒泡排序的话最多不会超过n^2/2次比较和交换，因此这个问题就是多项式级的复杂度。若是要求打印n个数字的所有全排列，那么至少也需要打印n!组数列，因此这个问题显然不是多项式级的复杂度。
对于很多问题，大家不知道多项式复杂度的解法是否存在。但是可以在多项式时间内验证一个解是否正确。一个典型的例子是汉密尔顿回路问题：给定一个图，需要找到能遍历所有点的回路且不会重复经过任何一个点。假设有人提出一条回路，只要沿着走一遍就可以看出对不对了，但是想要找到所有解或是证明无解，至今没有特别有效的算法。这类“能在多项式时间内验证解的正确性”的问题被称为NP。是否所有NP问题都有多项式解法呢？这个被称为“P=NP?”的问题粗看起来很可能是否定的（让科学家们进行的投票中，有85%的投票人认为答案是否定的），但实际上这个问题是著名的千禧年问题之一，在1950年就被提出了，至今仍然悬而未解。
即使无法笼统地确定P=NP是否成立，仍然出现了一个重要的概念：NP完全。1971年Steven Cook和1973年Leonid Levin独立证明了一个很重要的事实：所有NP问题都可以转化（“归约”）成布尔可满足性问题(SAT问题)。后者可以形象地描述为给定一个多输入，单一输出的逻辑电路，求何种输入可以使输出为真。换言之，SAT问题是NP问题里面最难的一个：一旦找到了多项式复杂的算法能解决SAT问题，所有NP问题就能迎刃而解。反过来说，如果能把SAT问题转化成某个其他的NP问题，那么这个新的NP问题也会具有同样的复杂度。科学家们给这类问题起了名字，叫做具有“NP完全”复杂度的问题。其中包含了大量经典或常用的问题，包括前述的汉密尔顿回路问题，旅行推销员问题，背包问题，0-1规划问题，等等。研究者们一方面试图找到或证明已有的问题不存在多项式复杂度的解法，一方面将越来越多的问题加入其中。
对三消游戏来说，输入规模即是给定盘面的大小，而主要问题则是如何在限定步数内使某个特定位置上的宝石消失。研究者们为各种逻辑门的组件构造了等价的宝石排列，并证明了在盘面足够大的情况下可以将任何3SAT问题（SAT的一种变形）的逻辑电路转化成对应的三消盘面。事实上，不光是三消游戏，包括超级马里奥和宠物小精灵在内的一些经典任天堂游戏也被证明拥有NP完全的复杂度。如果三消最后真的成为了P=NP的突破口，对游戏玩家来说会是个有趣的场景吧。
想想看，游戏党对买买买爱好者们说“你知道么，三消游戏和买哪些东西凑单最划算是一类的问题哦~”大概可以解决很多人生矛盾吧。
cite:arxiv/pdf/1403.5830.pdf
PS：如果你喜欢这个系列的漫画，欢迎关注公众号TILcomic~
