P vs. NP 五十年：AI正在解決不可解問題

AIGC動態歡迎閱讀

原標題：P vs. NP 五十年：AI正在解決不可解問題
關鍵字：問題,算法,量子,機器,計算機
文章來源：人工智能學家
內容字數：29711字

內容摘要：

來源：雷鋒網
作者：Lance Fortnow
編譯：Don
編輯：青暮
【轉載自雷鋒網，鏈接請點擊閱讀原文。此文有助于理解2023圖靈獎獲得者Avi Wigderson過去40年的工作重心：隨機性與難解性。順便說，我不是很認同編譯者給這篇文章所起的中文標題。原文標題是：Fifty Years ofPvs.NP and the Possibility of the Impossible。作者曾出版過一本專門談P/NP問題的科普書，中文版名為《可能與不可能的邊界——P/NP問題趣史》。】
P和NP問題一直是計算機領域的老大難問題，那么在近50年間，人們對這個問題有什么深入的研究呢？讓我們在本文中深挖這個世紀難題。在1971年5月4日，偉大的計算機科學家和數學家Steve Cook就在他的論文《定理證明程序的復雜性 The Complexity of Theorem Proving Procedures》中首次向世界提出了P和NP的問題。在50年后的今天，世人仍然在試圖解決這個計算機領域中最著名的問題。其實在12年前（2009年），我也曾經就該問題進行了一些討論，大家可以看之前的《P與NP

原文鏈接：P vs. NP 五十年：AI正在解決不可解問題

聯系作者

文章來源：人工智能學家
作者微信：AItists
作者簡介：致力成為權威的人工智能科技媒體和前沿科技研究機構