4.4 超越卡普的工作

在卡普的论文之后,计算机科学界掀起了一个寻找并证明各种问题是否属于NP完全的热潮。在接下来的几年里,教授和研究生们成功证明了许多已知的搜索问题(以及一些新问题)是NP完全的。一本1979年出版的书1中列举了三百多个主要的NP完全问题。NP完全问题持续在各个领域涌现,如计算机科学、物理学、生物学、经济学,以及其他许多攀登到困难顶峰的学科。Google学术搜索NP-Complete将返回超过138 000篇科研文献,时间跨度从1972年到2011年,单是2011年就有近1万篇。我们在此无法一一列举,只从中挑选几篇,看看这些文章是什么风格。

1 Computers and Intractability: A Guide to the Theory of NP-Completeness, 作者Michael Garey和David Johnson(New York: W. H. Freeman, 1979)。

1. 支配集(Dominating Set)

敌友国是否存在这样的50个人:其余的人和这50个人中的至少1个是朋友?NP完全问题。

2. 三角切分问题 (Partition into Triangles)

敌友国理工学院的每个宿舍只能容纳三名学生。我们能把所有敌人都安排在不同的宿舍里吗?NP完全问题。

3. 大规模数独游戏

数独(Sudoku)是一种起源于日本的填数字游戏,使用一个9×9的格子,如下图所示。

enter image description here

图4-2 数独

数独的游戏目标是填满所有空格,并使每一行、每一列和由黑线标出的3×3小方格中的数字分别是1到9的不重复的数字。

enter image description here

图4-3 数独的解

数独是NP问题,因为很好检查一个解。找到一个解有多难?不太困难。使用简单的回溯算法,普通计算机可以在几秒内找到一个有效解。

enter image description here

图4-4 大规模的数独

但是如果谜题的规模变得更大,像上面这个25×25的版本,要求每行、每列和小方块中填入A到Y且不重复的字母,会发生什么呢?

这回普通计算机就得算好长时间了,而100×100的数独游戏能打败当今最快的机器。

大规模的数独游戏是NP完全问题。你自认为是数独高手?如果你能可靠地解决大规模的数独,那么你也能解决可满足性问题、旅行推销员问题,还有其他几千个NP完全问题。

数独可不是桌面游戏中唯一一个NP完全问题。来看微软Windows系统自带的扫雷游戏。

enter image description here

图4-5 扫雷

每个小方块埋着一个数字或者地雷,数字代表临近的方块(包括水平、垂直和对角线相邻)总共有几个地雷。在某个不是地雷的方块上点一下会显示出下面的数字。如果你觉得方块下面有地雷,就标一个小旗子。点中地雷你就输了。判断能否玩赢一个大规模的扫雷游戏也是NP完全问题。这是上面那张图里剩下的地雷。

enter image description here

图4-6 扫雷失败

图4-7 俄罗斯方块

当然还有俄罗斯方块。玩家平移和旋转各种下落的积木,填满一行的那一刻整行会消失,游戏目标是不让整个画面都被方块填满,坚持尽可能长的时间。

积木分很多种形状。

图4-8 俄罗斯方块的积木

经典俄罗斯方块游戏中你不知道下一块积木的形状。但即使你提前知道了各种形状的积木到来的次序,如何把俄罗斯方块玩到最好也是一个NP完全问题。

谁曾想把数独、扫雷和俄罗斯方块这些游戏玩好,就可以证明P=NP从而解决我们这一代面临的最大的挑战呢?

enter image description here

图4-9 魔方。图片作者为Tom van der Zanden

魔方又怎么样呢?即使是3×3×3的小魔方,一般人也得花不少工夫才能知道如何复原,而求解更大的魔方的难度可想而知。

其实不算太难。我们对于解决更大规模的魔方复原问题有一些很快的算法,它们都基于一个叫做群论的数学分支。这些算法不能保证找到全局最少步骤的解法,但是总能找到足够短的方法,从任何可能的打乱方式开始将魔方复原。

与玩好俄罗斯方块、扫雷和数独的困难程度相比,复原魔方的问题容易得出奇。

而双人对战游戏,如国际象棋、跳棋、黑白棋和围棋,它们的难度又如何呢?这些游戏的大规模版本,其难度和可满足性问题等NP完全问题的难度是相当的。但是这些双人游戏不属于NP类问题。比如我告诉你,这盘国际象棋肯定是白方赢,最后一步是三列卒吃王,你根本没法验证我的话。计算机科学家基本上都认为国际象棋、跳棋、黑白棋和围棋的难度均大于任何NP问题。

4. 肾脏交换

正常人有两个健康的肾来将体内的代谢废物滤出体外。如果只剩一个肾,人还是可以过正常的生活。如果两个肾都不能用,就必须用透析来维持生命,这不仅需要耗费大量金钱和时间,而且时刻都有可能死亡。

有两个健康肾的人可以捐献出其中一个,挽救双肾衰竭的病人,前提是捐献者的肾和受捐者的身体相容。通过简单的抽血就可进行这种相容性测试。

假如Alice不幸双肾衰竭,她的丈夫Bob同意捐献自己的一个肾。如果Bob的肾和Alice的身体相容,那么可以通过手术将Bob的一个肾摘除并移植给Alice。

但Bob的肾有可能受到排斥。还有一线希望,就是所谓肾脏交换项目。

假如另一个人Charlie也需要肾,愿意为他捐肾的是他兄弟David,而David的肾也和Charlie不相容。然而,如果David的肾与Alice相容,并且Bob的肾和Charlie的肾相容,那么就可以安排让四人同时上手术台,这样术后每个人都有一个好肾,挽救两条生命。

假设我们有了关于上述这样潜在的肾脏捐献者-接受者的数据库,就可通过有效的算法,让尽可能多的两对捐献者-接受者成功配对,达成肾脏交换。基本上这就是前一章介绍过的配对问题,很容易解决。

不止是两个人,还可以有更多人来配对。2011年年末,60场手术为30位患者移植了健康的肾脏,这是通过其他任何方法都不可能做到的。

然而如果允许多于两对的捐献者-接受者互换肾脏,如何找到尽可能多的多人搭配方案在目前还是一个NP完全问题。P=NP的证明在这里是性命攸关的,可比如何玩好扫雷重要得多。

目录