1.3 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万美元的人最好去玩彩票,那样把握更大一些。

目录