寻找金券

一个糖果厂老板决定推出一个活动,将五张金券藏到巧克力的包装里,而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。如何找到这些金券?你可以买尽可能多的巧克力。你可能会试试用磁铁,可惜金没有磁性。或者你可以雇佣数千人,让他们每人筛查一小堆巧克力。

旅行推销员问题

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

划分难题

看下边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个数字之和为2 000 000。你能把它们平分成两组,每组19个数字之和分别为1 000 000吗?

你的手是最不可思议的工程装置,它能戳、抓和指,能系鞋带,能射箭,还能弹钢琴、拉小提琴,能变戏法,能驾驶车、船、火车或飞机。一只手有27块骨头,5根手指。手具有结构复杂的神经、肌腱和肌肉,这些都包裹在富有弹性的皮肤里。然而,这一不可思议的装置,自然造物的杰作,却不能自己做事,而只能执行人脑的指令。 然而我们的脑就能控制手。可以将脑看作一个性能强大的计算机,如果脑能控制手去系鞋带或是创作艺术,那么计算机程序也一定能。知道这样的程序存在并不意味着就能找到它们。随着时间的推移,计算机科学家肯定会写出更精深的程序,松冈的机械手将能执行更复杂的活动。这肯定是一个精彩的旅程,但也可能进展缓慢、举步维艰。

一定要这样缓慢吗?想象一下,只要我们简单描述一项任务,马上就会有一个程序提供相应的功能;给计算机输入一段演示人如何打结的电影,然后它立刻就能用机械手重复打结的过程;把莎士比亚全集录入计算机,然后它就能创作一部新的“莎士比亚”戏剧;只要我们能认出某个东西,就能找到它。这些梦想都能成真——前提是P=NP。

P/NP问题的魅力就在这里。究竟能否让所有的事都变得易如反掌?还是说,有些事情注定就没有简单的解决方法?不能排除这种可能性。无论如何,我们并不指望着生活会那么简单。尽管我们并不认为P=NP,但这么美好的世界却让我们忍不住充满憧憬

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

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

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

  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年被格里高利•佩雷尔曼解决,但他婉拒了100万美元的奖金。截至本书写作时其他6个难题都尚未解决。

解决P/NP问题就能拿到100万美元,这可是货真价实的金券啊!

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