一个糖果厂老板决定推出一个活动,他将五张金券藏到巧克力的包装里,而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。

如何得到这些金券?你可以买尽可能多的巧克力。你可能会试试用磁铁,可惜金没有磁性。或者你可以雇佣数千人,让他们每人筛查一小堆巧克力。听起来很傻,但是小姑娘维鲁卡?咸咸就要这么做,因为她特别想得到一张金券,去参观威利?旺卡的巧克力工厂。

维鲁卡的父亲咸咸先生是个富商,他决定买光他能找到的巧克力。这还不够,就算有堆积如山的巧克力,要从中找到小小的金券也很困难。咸咸先生也有一家工厂,他不惜动用工厂的工人,终于找到了一张金券。他对记者讲述了找到金券的过程:

“我是做花生生意的,知道吧,我有大约一百个女工,为我剥花生用来烤和腌制。她们整天就坐在那,剥花生。所以我跟她们说,“好了姑娘们,”我说,“你们不要剥花生了,开始给我剥这些破糖纸吧!”然后她们就剥。我让工厂的每一个工人都卯足了劲地撕掉巧克力的包装纸,从早干到晚。”

“但是三天过去了,我们还是没走运。哦,那可真够呛!我可怜的小维鲁卡越来越暴躁,每次我一回家她就朝我嚷嚷:‘我的金券在哪!我要我的金券!’她撒泼又打滚,踢腿又叫喊,实在招人烦。我可不希望看到我的小宝贝这么不高兴,所以我决定一直找, 不找到她要的东西誓不罢休。终于,在第四天的晚上,一个女工大叫,‘我找到了!金券!’然后我说,‘把它给我,快!’她给了我,然后我跑着回了家把它交给亲爱的维鲁卡, 她高兴得合不拢嘴。我们家又一次变得其乐融融了。”

和咸咸先生一样,无论你打算怎么找那张金券,你都需要很多时间、钱,或者运气。也许有一天,有人能发明出一个快速找到金券的便宜装置,也许这样的装置并不存在。

然而,1000万对于今天的计算机来说只是很小的数字。如果你把糖果数字化,录到一个数据库里,现在的电脑只用不到一秒就能把它找一遍。虽然计算机比人快得很多,但是它面对的问题规模也比在糖果里找金券大得多。

现在最大的电子数据集合规模有多大?比如,整个互联网,考虑到所有视频、音频、电子邮件及其他一切,总的信息量差不多有100,0000,0000,0000,0000字节,最多相差几个0。一个字节大致对应键盘上的一个字符。这个数很大,但记住,计算机也很快。一般的笔记本电脑每秒可以执行1万亿个操作,这样算来,理论上只需要不到4个月就能搜完整个互联网的内容,前提是你能把整个互联网装到你电脑的内存里。Google每时每刻都在搜索整个互联网,它使用了几十万台快速的计算设备。

如果计算机可以很快地搜遍整个互联网,看起来好像我们就解决了这个找金券问题的电子版。但是,计算机不仅要帮人们搜索已有的数据,还要搜索问题的所有可能解。

认识一下可怜的旅行推销员Mary,她来自华盛顿特区,为美国木槌集团公司工作。她需要从家乡旅行到48个州的首府,向各州法院推销木槌。木槌公司为了削减成本,让Mary找到通过所有城市的最短路径。Mary画了一张图,写写画画了一会儿,制订了一个不错的路线。

总距离=1,1126英里

enter image description here

图1-1 旅行推销员问题的地图

差旅部门的人想让Mary试试能否找到另一条路线,把路程缩短到1,1000英里以下。Mary写了个计算机程序,试图穷举所有可能的路线,找出最短的一条,但是一周以后,程序还没跑完。Mary坐下来开始算数。作为第一个站的城市有48种选择,然后从剩下47个城市中选一个作为第二站,再从剩下的46个城市中选一个,依此类推。可能的路径共有48x47x46x…x2x1种,也就是下面这个62位数:

12,4139,1559,2536,0726,7086,2289,0473,7337,5038,5214,8635,4677,7600,0000,0000

即使计算机计算一条路线长度的时间等于光通过一个原子直径的时间(大约0.00000000000000000033秒),仍然需要十亿亿亿倍于宇宙年龄的时间才能算完。难怪Mary的电脑算了一周还没有完。Mary想知道有没有比穷举更好的方法找到最好的路线,就像在所有可能行程的“巧克力山”里面刨出那张小小的金券。

这就是本书最基本的问题——P/NP问题。其中的一个实例,就是能否为旅行推销员找到最短路径。P和NP自有其十分专业的定义,但是把他们看作概念比看作数学对象更好。“NP”是存在我们要找的解的问题的集合。“P”则由我们能很快找到解的问题构成。“P=NP”意味着我们能总是很快地计算出任何问题的解,当然也包括找到旅行推销员的最短路径。相反“P≠NP”意味着我们不能。

1.1 划分的难题

看下边38个数字:

14,175, 15,055, 16,616, 17,495, 18,072, 19,390, 19,731, 22,161, 23,320, 
23,717, 26,343, 28,725, 29,127, 32,257, 40,020, 41,867, 43,155, 46,298,     
56,734, 57,176, 58,306, 61,848, 65,825, 66,042, 68,634, 69,189, 72,936,     
74,287, 74,537, 81,942, 82,027, 82,623, 82,802, 82,988, 90,467, 97,042,     
97,507, 99,564。

这38个数字总和为200,0000。你能把它们平分成两组,每组19个数字的总和为100,0000吗?你可以使用计算器、电子表格或写一个计算机程序。(答案在本章最后。)

不怎么简单,是吧。把这些数分成两组有170亿种方式。如果编程得当,你可以在今天的快速计算机上找到答案。但是要是我给你3800个数,或者3800万个数呢?短小的计算机程序可没法给你答案了!

这只是个无意义的数学谜题吗?就算存在一个厉害的计算机程序,它能解决这个平分数组的问题(假设有解),那又如何呢?如果是这样的话,我们能用这个程序做更多的事。这个程序能解决所有的问题,包括旅行推销员问题在内。这个简短的难题抓住了P/NP问题的本质:一个程序如果能解决这个难题的大规模版本,它也能解出任意的问题。

1.2 手

你的手是最不可思议的工程装置。手能戳、抓和指。手能系鞋带,能射箭。手可以弹钢琴、拉小提琴,变魔术戏法,开车、船、火车或飞机。你的手可以握住其他人的手,或和他们玩拇指相扑。手可以比划出信号语言,也能通过写字或打字来交流。手可以轻抚,也能重击。手可以使用钟表匠的精密工具,也能操作链条锯。有才华的双手可以创造艺术杰作,写出音乐或诗歌。人类取得的几乎所有成就,都离不开人们的双手。

一只手有27块骨头,5根手指,包括最重要的拇指。结构复杂的神经、肌腱和肌肉,包裹在富有弹性的皮肤里。然而,这一不可思议的装置,这自然造物的杰作,却不能自己做事。它只能执行脑的指令。死人的手平平无奇,做不了任何事情。

手就是自然的硬件,硬件本身不能做什么。手需要软件即脑的指令来告诉它,如何执行和实现脑希望手做的事情。

Yoky Matsuoka是华盛顿大学的机器人学教授,她带领科研小组制作出了一个解剖学意义上准确的机械手,其手指有和人类手指同样的动作自由度。理论上她的机械手能完成人手能做的任何事情,但是实际上,它只能完成很简单的任务,因为写一个计算机程序来全方位控制Matsuoka的机械手,是非常复杂的。在协调多块肌肉的运动时,即使是完成最简单的任务,也需要很复杂的代码。

然而我们的脑就能控制着我们的手。脑可以看作是一个性能强大的计算机,如果脑能控制手去系鞋带或是创作艺术,那么计算机程序也一定能。

知道这样的程序存在和找到它们是两码事。随着时间的推移,计算机科学家将会写出更精深的程序,Matsuoka的机械手将能做出更复杂的活动。这将是一个精彩的旅程,但可能也是举步维艰、进展缓慢的旅程。

一定要这样缓慢吗?假设我们只要简单描述一项任务,马上就有一个程序提供相应的功能。给计算机输入一段表现人如何打结的电影,然后立刻让它用机械手重复打结的过程。给计算机看莎士比亚全集,然后让它创作一部新的“莎士比亚式的”戏剧。假设我们只要能辨认出某个事物,就能找到它。以上这些假设都将成真——如果P=NP。

P/NP问题的魅力就在这里。究竟能否让所有的事都变得易如反掌?还是说,有些事情注定没有简单的解决方法?我们无法排除这种可能性。那样的话生活就太简单了,我们不能寄希望于此。尽管我们不认为P=NP,但是对这样一个美好世界的憧憬让我们欲罢不能。

1.3 P/NP问题

P/NP问题讨论的是以上所述的所有问题,以及许多与之类似的问题。它们归根到底都是在问:我们搜索大量的可能性的速度能有多快?我们找到“金券”即最佳答案的过程能变得多容易?

P/NP问题的首次提出,是在一封1956年的库尔特?哥德尔(Kurt G?del)寄给约翰?冯?诺依曼(John von Neumann)的信中,两位都是20世纪最伟大的数学泰斗。 这封信后来不幸遗失,后来在20世纪80年代又被找到。P/NP问题在学术界的亮相是在20世纪70年代初,由史蒂夫?库克(Steve Cook)和列昂尼德·莱文(Leonid Levin)独立提出,当时两位分别所在的国家正在进行冷战。之后理查德?卡普(Richard Karp)列出了这个领域中的21个重要难题,包括前面提到的旅行推销员难题和划分难题。计算机科学家从卡普的工作开始认识到P/NP问题极为重要,由此计算机科学研究的方向发生了戏剧性的转变。如今,P/NP问题的关键性作用已经不仅限于计算机科学领域,还延伸到其他许多领域,如生物学、医学、经济学和物理学。

P/NP问题已成为所有数学领域最难的开放问题之一。1994年安德鲁?威尔斯(Andrew Wiles)证明了费马大定理(Fermat's Last Theory), 受这一消息的鼓舞,克雷数学研究所决定举办竞赛,攻克他们认为最为重要而尚未解决的数学难题。2000年,他们列出了下面这7个千禧年难题,并为每道难题的攻破设立了1百万美元的奖金。

  1. 贝赫和斯维讷通-戴尔猜想 (Birch and Swinnerton-Dyer conjecture)
  2. 霍奇猜想(Hodge conjecture)
  3. 纳维-斯托克斯方程(Navier-Stokes equations)
  4. P/NP问题 (P versus NP)
  5. 庞加莱猜想(Poincaré conjecture)
  6. 黎曼假设(Riemann hypothesis)
  7. 杨-米尔斯理论(Yang-Mills theory)

千禧年难题中的庞加莱猜想已于2003年被格里高利?佩雷尔曼(Grigori Perelman)解决,但他婉拒了1百万美元的奖金。截止本书写作时其他6个难题尚未解决。

解决P/NP问题就能拿到1百万美元,果真是金券啊!

更好的是,如果你能证明P=NP,那么你也就掌握了找到金券的秘诀,解决其余的千禧年难题将是举手之劳。也就是说证明P=NP,你就能解决6道千禧年难题并得到6百万美元。然而证明P=NP或P≠NP可没那么容易。一心想得到6百万美元的人最好去玩彩票,那样把握更大一些。

1.4 找到金券

有时候我们能够找到金券。比如我在芝加哥,想开车去纽约城,往车载GPS里输入地址,一两分钟之内它就能给出一条从芝加哥到纽约的最快的路线,然后我就踏上旅程。几个MB的内存便可容纳全部的美国街道地图,但地图中可能的路线数量要多的多。从芝加哥到纽约的所有可能行车路线有多少条?不开错方向的情况下,通过一点信封背面就能做的数学运算,可以得出不同的路线数目大于1个vigintillion,即1后边跟63个0。 GPS根本没有时间检查所有的可能性,但还是能找到最快的路线。

旅行时间有一个有趣的性质。随便选一个中间地点,比如匹兹堡。从芝加哥经过匹兹堡到纽约的最短路线,一定是芝加哥到匹兹堡最短路线,接上匹兹堡到纽约的最短路线。不走匹兹堡可能有更快的路线,但是芝加哥到纽约的最短路线,绝不会比从芝加哥经过匹兹堡到纽约的最短路线还要长。

GPS的计算机程序正是利用了这个性质,快速缩小搜索范围并找到了最佳路线。可能仍需要检查上亿条路线,但是GPS的计算机处理器完全能胜任,毕竟要比总数的那个天文数字要小得多。

找到最短路径的并没有体现出P/NP问题的全部力量。最短路径问题告诉我们,全部的可能性数量特别大,并不总意味着我们必须遍历它才能找到答案。P/NP问题其实是问,是不是对于任意给定的搜索问题,我们都不必遍历所有的可能性就能找到答案?

1.5 漫漫长途

这本书讲的是P和NP的故事。你会了解到什么是P和NP;它们描述的是哪类问题;所有搜索问题中最难的问题——NP完全问题是怎么回事;以及NP完全问题对抓住P/NP问题的本质有何作用。

举一个简单的例子:Facebook上由一群互为好友的人组成的集合即团(clique)中, 最大的包含多少人? 有1百人,还是1千人?即使你拥有Facebook的全部数据,这个问题也很难求解。求解较大规模的团问题的困难程度,不低于任意的搜索问题。

如果P=NP会怎么样?那么我们将迎来一个美好的世界,计算所有的事物都将易如反掌。我们能快速地了解一切,揭开世界上所有事物的神秘面纱,从治愈绝症到洞悉宇宙的本质。美好的世界也有它灰暗的一面,人们将丧失隐私、丢掉工作,因为没有什么是计算机不能知道或达成的。

这样美好的世界不太可能会到来。困难的搜索问题仍将存在,我们想要甚至需要找到它们的答案。其实我们大可不必放弃。计算机科学家已研发出了许多技术,包括很有可能对许多问题奏效的启发式方法,以及能给出接近理想解的近似技术。

P和NP问题是如何产生的?这个故事发生在世界被冷战分隔开来的那段日子,其实可以把它分成两个故事来讲。有关高性能计算的思路和问题分别在两个世界里独立发展,而最终双方的研究之路殊途同归,这就产生了P/NP问题。

我们如何着手证明P ≠ NP?库尔特?哥德尔证明数学不能解决所有的问题。能否用类似方法,证明存在不能快速解决的搜索问题?为了分析问题的复杂度,我们可以把计算问题的过程分解为最基本的组成单元。数学的抽象分支之一,算术几何学,为人们能在有朝一日解决这个重要的问题带来了新的希望。但我们距离那一天还很远。

P ≠ NP会带来什么好处呢?我们能借此保守秘密,产生看上去真的随机的伪随机数。

基于量子力学的未来计算机是否会让P/NP问题变得无足轻重?不太可能,尽管量子计算机的建成,将解决一部分现在计算机束手无策的问题,比如大数的因数分解。量子力学也可能透露P是否等于NP的玄机。

未来将会如何呢?我们仍将面临计算领域的巨大挑战。人们如何与互相协作处理问题的计算机打交道?如何分析每天人们产生的海量数据?所有事物都能联网,世界将会怎样?在解决这些问题的未来,P/NP问题只会变得更为关键。

1.6 划分难题的解

以下38个数

14,175, 15,055, 16,616, 17,495, 18,072, 19,390, 19,731, 22,161, 23,320,
23,717, 26,343, 28,725, 29,127, 32,257, 40,020, 41,867, 43,155, 46,298,
56,734, 57,176, 58,306, 61,848, 65,825, 66,042, 68,634, 69,189, 72936, 
74,287, 74,537, 81,942, 82,027, 82,623, 82,802, 82,988, 90,467, 97,042,
97,507, 99,564

可分成如下两组:

15,055, 16,616, 19,390, 22,161, 26,343, 40,020, 41,867, 43,155, 46,298,
57,176, 58,306, 65,825, 66,042, 69,189, 74,537, 81,942, 82,623, 82,988,
90,467

14,175, 17,495, 18,072, 19,731, 23,320, 23,717, 28,725, 29,127, 32,257, 
56,734, 61,848, 68,634 72,936, 74,287, 82,027, 82,802, 97,042, 97,507, 
99,564。

每组中数字总和都是100,0000。

注:本文摘自图灵新书《金钥匙:计算机算法的历史与P/NP问题》第1章译稿(未经编辑)。