鑽石舞台

P和NP問題一直是計算機領域的老大難問題，那麼在近50年間，人們對這個問題有什麼深入的研究呢？讓我們在本文中深挖這個世紀難題。

作者 | Lance Fortnow

編譯 | Don

編輯 | 青暮

在1971年5月4日，偉大的計算機科學家和數學家Steve Cook就在他的論文《定理證明程序的複雜性 The Complexity of Theorem Proving Procedures》中首次向世界提出了P和NP的問題。在50年後的今天，世人仍然在試圖解決這個計算機領域中最著名的問題。其實在12年前（2009年），我也曾經就該問題進行了一些討論，大家可以看之前的《P與NP問題的現狀》綜述。

文章地址：Fortnow, L. The status of the P versus NP problem. Commun. ACM 52, 9 (Sept. 2009), 78–86. https://doi.org/10.1145/1562164.1562186

計算機理論在近些年並沒有得到很大的發展。從2009年那篇文章發表以來，P與NP問題及其背後的理論並沒有發生顯著的變化，但計算世界確實發生了變化。比如說雲計算，就推動了社交網絡、智能手機、經濟、金融科技、空間計算、在線教育等領域的飛速發展。更重要的是，雲計算還幫助了數據科學和機器學習的崛起。

在2009年，世界前10大科技公司中出現了一家獨大的場面——微軟公司獨孤求敗。但是截至2020年9月，市值前七名的公司分別是蘋果、微軟、亞馬遜、Alphabet（谷歌）、阿里巴巴、Facebook和騰訊，彼此平分秋色。不光是大公司的變革明顯，計算機人才的需求量也是如此。據統計，在2009到2020年間，美國的計算機科學專業畢業生的數量增加了三倍有餘，但這還是無法滿足市場上對該領域人才的需求量。

P和NP的問題作為數學界和計算機界的一個難題來源已久，它被列入克萊數學研究所的千年難題之一。而且這個組織還為能夠攻克該問題的研究人員提供了上百萬美元的獎金懸賞。我會在文章的末尾用一些例子來解釋P和NP問題，這雖然沒能讓我們從本質上對其有更多的認識，但是也能看出來P和NP的很多思考和成果推動了這個領域的研究和發展。

(繼續閱讀...)

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

微博@地球知識局

前兩天剛寫了🔗中老鐵路通車，立馬又迎來了另一樁鐵路界的喜事，那就是12月6日開通的張吉懷鐵路，昭示着湖南湘西正式邁入高鐵時代，在這裡也要給這位參與鐵路建設的讀者點個讚！

(繼續閱讀...)

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()