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万美元的奖金。

• 贝赫和斯维讷通-戴尔猜想（Birch and Swinnerton-Dyer conjecture）
• 霍奇猜想（Hodge conjecture）
• 纳维-斯托克斯方程（Navier-Stokes equations）
• P/NP问题（P versus NP）
• 庞加莱猜想（Poincaré conjecture）
• 黎曼猜想（Riemann hypothesis）
• 杨-米尔斯理论（Yang-Mills theory）

千禧年难题中的庞加莱猜想已于2003年被格里高利·佩雷尔曼解决，但他拒绝了100万美元的奖金。截至本书写作时其他6个难题都尚未解决。

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

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