4.5 漏网之鱼

人们在20世纪70年代所研究的大部分NP问题,都要么被认定属于NP完全问题,要么被有效解决,从而归属于P。但还是有一些NP问题冥顽不灵,难以确定其归属。这些问题中的一部分在很多年后被解决了,另一部分直到今天都还没有被定性,成为漏网之鱼。

1. 图的同构问题

在敌友国流行着一个叫“刀剑征程”(Blade Quest)的MMORPG(大型多人在线角色扮演游戏)。游戏中每个玩家都会起一个新名字,操纵一个虚拟角色(avatar)去和其他玩家的虚拟角色进行互动。敌友国的敌友关系也被引入了刀剑征程的世界。在现实中互为朋友的居民,他们在游戏中的虚拟角色也是朋友关系;相反,现实中的敌人在游戏里也是敌人。

Isabel、John、Kevin、Laura、Molly和Nancy是几个喜欢玩刀剑征程的敌友国居民。

enter image description here

图4-10 玩刀剑征程的居民

这6个人在游戏中的虚拟角色的名字是Achris、Bolem、Chyrard、Degarald、Enthrr和Fev,但是哪个虚拟角色对应哪个真人是保密的。在刀剑征程中,这几个虚拟角色也有一个好友关系图。

enter image description here

图4-11 刀剑征程中的虚拟角色

Laura看了这两张图,就在游戏里给别的玩家发了一个消息:“我知道你在现实中是谁。”你能猜出来吗?

这两张图存在唯一的对应方式,即Isabelle在游戏中对应的虚拟角色是Enthrr,John是Degarald,Kevin是Chryard,Laura是Bolem,Molly是Achris,还有Nancy是Fev。我们可以验证一下,如Molly在敌友国的朋友是Laura和Nancy,与之对应,在刀剑征程中Achris的朋友是Bolem和Fev。

好友关系图之间的映射被称为图的同构问题。有可能存在多种映射,也可能不存在,这取决于给定的图集。图的同构性属于NP类问题:如果知道了谁对应谁,你可以通过逐对查看好友关系在两张图中是否一致来验证这个解的有效性。

但是图同构是否属于P,即我们是否能找到图之间的映射(假设存在)的有效算法,还是未知的。我们也不确定图同构是NP完全的,而出于多种技术原因,计算机科学家也不认为它是NP完全的。图同构属于另一小撮问题,其难度比P问题大,但比不上哈密顿回路、最大割等NP完全问题。

2. 质数和因数分解

你可以对15进行因数分解,得出15×1或5×3。24这个数可等于24×1、 12×2 、8×3或6×4。但是你只能把17写作17×1。17是一个质数,即只能把它写作1和自身乘积的数。最开始的几个质数是2、3、5、7、11、13、17、19。质数有无限多个。已知的最大质数(在我写作之时)是一个12 978 189位的数,它开始的几位是316 470 269 330 255 923 143 453 723…

怎么判断一个数是否是质数?例如要判断1 123 467 619是否是质数,你需要遍历所有小于1 123 467 619的数,看看是否有能整除它的数。事实上你只需要检查到33 518(1 123 467 619的平方根)就可以了。听起来是挺快,可是你如何判断下面这个数是否为质数?

8 273 820 869 309 776 799 973 961 823 304 474 636 656 020 157 784 206 028 082 108 433 763 964 611 304 313 040 029 095 633 352 319 623

早在古希腊就出现了判定质数的算法,但直到20世纪70年代才出现对几百位数有效的算法。这些算法基于数学中一个叫数论的领域的研究成果,在检查时需要使用随机生成的数。虽然这些算法在实践中表现很好,但是不依赖于随机生成数的质数判定算法直到2002年,才由一位印度教授曼尼达·阿加拉瓦尔带领他的学生尼拉吉·卡亚尔和尼汀· 萨克斯纳发现,从而把该问题归属于P类问题。

这些算法虽然能告诉我们

8 273 820 869 309 776 799 973 961 823 304 474 636 656 020 157 784 206 028 082 108 433 763 964 611 304 313 040 029 095 633 352 319 623

这个数不是质数,但令人惊奇的是,它们不能告诉你这个数的因子有哪些,也就是说不能对其因数分解。

我们有判定质数的有效算法,但是没有分解因数的有效算法。

因数分解是一个NP问题,因为如果你看到了
84 578 657 802 148 566 360 817 045 728 307 604 764 590 139 606 051

97 823 979 291 139 750 018 446 800 724 120 182 692 777 022 032 973
这两个数,把它们相乘就可验证乘积等于上面的
8 273 820 869 309 776 799 973 961 823 304 474 636 656 020 157 784 206 028 082 108 433 763 964 611 304 313 040 029 095 633 352 319 623

计算机科学家认为因数分解不属于P类问题,也觉得它不是NP完全问题。它是很难,但不像可满足性问题或地图填色问题那样难。

不只是喜欢摆弄数字的数学家们认为质数判定和因数分解问题很重要。现代密码学的许多方法都依赖于某些难以分解因数的大数,这是第8章的话题。

3. 线性规划

敌友国有一个熟食店叫Frenemy Fancy Franks,里面出售四种口味的香肠:法兰克福香肠、意大利香肠、德国香肠和西班牙香肠。不同种类的香肠制作时间不同,售价也有差别。Frenemy Fancy Franks应该如何安排每种香肠制作的数量,以获取最大的利润呢?

找到最优的方案就是在满足各种限制条件的前提下使收入最大化。假设制作一根法兰克福香肠的成本是1美元,意大利香肠的成本是2美元,德国香肠是3美元,西班牙香肠是4美元,且每日的总预算是1万美元。那么,1乘以法兰克福香肠的数量,加上2乘以意大利香肠的数量,加上3乘以德国香肠的数量,加上4乘以西班牙香肠的数量,结果应不超过1万。

在这类条件下进行最优化选择的问题叫做线性规划。可能的解集在高维空间形成一个几何体,叫做多面体。

早在1947年,格奥尔格·丹齐克发明了单纯形法(simplex method),这种方法能很快解决线性规划问题。单纯形法遍历多面体所有的边,直到找出最佳的解集。

既然有了单纯形法,我为什么要把线性规划放在(20世纪70年代)未分类的问题里面呢?因为在某些罕见的个例中,单纯形法无法快速求解线性规划问题。

1979年,利奥尼德·卡奇安发明了椭球算法(ellipsoid algorithm),基本思路是把多面体切分成越来越小的块,不断缩小范围并最终找到最优解。卡奇安给出了椭球算法有效性的证明,从而把线性规划分到了P类问题中。然而实践中椭球算法的耗时比单纯形法要长很多。虽然缺乏实用性,但椭球算法在之后的几十年中启发了许多更复杂的算法的诞生,因而它在学术上还是很有影响力的。

enter image description here

图4-12 多面体

这样一来,线性规划在理论和实践上分别都有了好的解决算法——只不过是两种非常不同的算法。

1984年,纳伦德拉·卡马卡发明了内点算法(interior point algorithm)。和单纯形法类似,卡马卡的算法遍历多面体,只不过是在内部遍历而不是表面。和椭球算法一样,内点算法也能将线性规划归属到P类,并且在经过优化后该算法的实际性能甚至高于单纯形法。

以上就是解决线性规划问题的三种非常不同的算法。第一种(单纯形)在实践上表现很好。第二种(椭球)在理论上很好。而第三种(内点)则在理论和实践上的表现都很好。能对一个在20世纪70年代末还被认为是未解决的问题给出这三份答案,是很值得人们为之自豪的进步。

目录