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万美元,这可是货真价实的金券啊! 更妙的是,如果你能证明 ,那么你也就掌握了找到金券的秘诀,解决其余的千禧年难题将是举手之劳。也就是说,证明了 ,你就能解决6道千禧年难题,并得到600万美元。然而证明 或 可没那么容易。一心想得到600万美元的人最好去玩彩票,那样把握更大一些。
可能与不可能的边界——1.3 P/NP问题
书名: 可能与不可能的边界
作者: [美] Lance Fortnow
出版社: 人民邮电出版社
原作名: The golden ticket:P,NP,and the search for the impossible
副标题: P/NP问题趣史
译者: 杨 帆
出版年: 2014-1
页数: 160
定价: 39.00
装帧: 平装
ISBN: 9787115335661