引言

?今天我們先放松一下，這篇文章并不是Java課程的學(xué)習(xí)，而是帶大家認(rèn)識一個(gè)學(xué)術(shù)問題。但是請大家放心，這里并不是學(xué)術(shù)的探討，因?yàn)槲乙膊欢?，我只是搜集一些相關(guān)的資料帶大家了解一下這個(gè)問題。更多的是出于滿足一下各位的好奇心。。。

天才基本法

?相信大家應(yīng)該都知道最近有一部劇非?；稹?strong>天才基本法，由雷佳音、張子楓、張新成主演的由同名小說改編的電視劇。

?該劇具體講了什么內(nèi)容我就不在這里詳細(xì)說了，相信有好多小伙伴都已經(jīng)刷完了(反正我已經(jīng)刷完了，確實(shí)不錯(cuò)，值得推薦)，沒有看的小伙伴也很值得一看。
?我們今天只研究劇中提到的P=NP?問題，芝士世界的老林和裴之共同證明了P=NP完全成立，這也使得芝士世界的計(jì)算機(jī)、醫(yī)療、環(huán)保等多個(gè)領(lǐng)域得到了跨越式的發(fā)展。
?而草莓世界的老林用盡二十多年的時(shí)間都沒有能夠證明，最后也只是在芝士裴之的幫助下證明了圖同構(gòu)是NP類問題的證明，這只是證明P=NP的一個(gè)階段性勝利。。。
?那我們就了解一下究竟P=NP？是個(gè)什么樣的問題？

回到目錄…文章來源地址http://www.zghlxwxcb.cn/news/detail-457070.html

什么是P/NP問題？

?P/NP問題是克雷數(shù)學(xué)研究所高額懸賞的七個(gè)千禧年難題之一，同時(shí)也是計(jì)算機(jī)科學(xué)領(lǐng)域的最大難題，關(guān)系到計(jì)算機(jī)完成一項(xiàng)任務(wù)的速度到底有多快。

?P/NP問題是Steve Cook于1971年首次提出。

?P指多項(xiàng)式時(shí)間（Polynomial），一個(gè)復(fù)雜問題如果能在多項(xiàng)式時(shí)間內(nèi)解決，那么它便被稱為P問題，這意味著計(jì)算機(jī)可以在有限時(shí)間內(nèi)完成計(jì)算；

?NP指非確定性多項(xiàng)式時(shí)間（nondeterministic polynomial），一個(gè)復(fù)雜問題不能確定在多項(xiàng)式時(shí)間內(nèi)解決。

?假如NP問題能找到算法使其在多項(xiàng)式時(shí)間內(nèi)解決，那說明它轉(zhuǎn)變成了P類問題。

有點(diǎn)難以理解，那就拿股市舉個(gè)例子：

?昨天某只股票收盤價(jià)為10元，今天收盤價(jià)為11元。漲幅是多少？
?我們很容易就可以通過公式計(jì)算出來，(11-1)/10=10%，這就是P類問題。

?那再請問，明天的收盤價(jià)是多少？是漲還是跌？
?這個(gè)問題我們不能通過一個(gè)具體的算法得到答案，只有等到了明天才能驗(yàn)證得到正確答案，這就是NP類問題。

?P/NP問題就是研究能否把NP類問題轉(zhuǎn)變?yōu)镻類問題。如果能，則P = NP 成立；否則，P != NP。

回到目錄…

P = NP 成立嗎？

?我們先假設(shè)P = NP成立，那么給這個(gè)世界帶來些什么影響呢？

?如果P=NP真的成立，那么對于任何一件隨機(jī)的事件，我們都可以找出針對性的算法來計(jì)算或控制事件的走向。還是剛剛那個(gè)股市的例子，我們就可以計(jì)算出每支股票在未來的漲跌情況，這樣豈不成了“股票之神”？在醫(yī)療上，我們可以解決很多目前無法攻克的疾病如癌癥；在科技上，我們可以通過特定的算法來解決我們無法實(shí)現(xiàn)的技術(shù)難題；總之無論在哪個(gè)領(lǐng)域都會取得很大的突破。毫不夸張地說，甚至有可能做到跨越時(shí)間、空間，知曉未來、洞察于千里之外。
?當(dāng)然，也存在一定的弊端，如對密碼學(xué)的影響，破譯密碼會變得很容易。甚至?xí)τ?jì)算機(jī)網(wǎng)絡(luò)安全構(gòu)成巨大的威脅。

?這雖然聽起來好像很扯淡！但確實(shí)有很大一部分?jǐn)?shù)學(xué)家和科學(xué)家在一直研究這個(gè)問題。那到底 P = NP 能否成立？有沒有人證明了它的成立？或是證明了它不可能成立？

學(xué)術(shù)界的最新消息：

公元2010年：
?8 月 6 日，HP LAB的 Vinay Deolalikar 教授宣布證明了P!=NP，并且公布了證明過程。
?8 月 8 日，Lipton 在博客上討論了這篇論文，給出了略顯樂觀的評價(jià)：這是一個(gè)值得認(rèn)真對待的證明。這篇文章引來大量嚴(yán)肅的學(xué)術(shù)性回復(fù)，大多來自業(yè)內(nèi)人士，各方看法不一。
?8 月 9 日，Lipton 寫了一篇新的博客文章，指出了 Deolalikar 證明思路中的一些重大漏洞。
?8 月 10 日，Lipton 寫了新的博客文章，試圖將各方討論的結(jié)果以更清晰的方式呈現(xiàn)出來。同日，Deolalikar 在自己的網(wǎng)站上撤下了論文初稿的鏈接，稍后放上了新一稿。
?8 月 11 日，Lipton 貼出了 Deolalikar 對一部分學(xué)術(shù)質(zhì)疑的答復(fù)。Vinay Deolalikar 貼出了論文的第三稿。
?8 月 12 日，Lipton 貼出了一封來自 Neil Immerman 的信，指出了兩個(gè)此前未被認(rèn)真討論的漏洞。
?8 月 13 日，Deolalikar 貼出了一篇關(guān)于自己的證明的解釋性文檔。
?8 月 14 日，在很多科學(xué)家的共同討論中，人們逐漸理清 Deolalikar 的論文的根本問題在于把兩個(gè)沒有在論文中被嚴(yán)格定義出來的直觀概念混淆在一起，從而做出了不完善的論證。
?8 月 15 日，Lipton 貼出了他對于一周以來討論的總結(jié)：Deolalikar的證明不能成立。隨后的發(fā)言越來越多地集中于更抽象的層面，并且仍在繼續(xù)。

回到目錄…

總結(jié)

?截至到目前為止，P = NP? 問題的討論還沒有停止。沒有人能拿出有力的證據(jù)證明等式成立。雖然有科學(xué)家拿出自己的論據(jù)來證明了P != NP，但是隨后也發(fā)現(xiàn)了論據(jù)的漏洞，依然不能證明等式不成立。現(xiàn)在 P = NP? 依然是個(gè)謎！
?也許在很多人看來這個(gè)問題的討論沒有任何意義，覺得可能會走在一條錯(cuò)誤的道路上。但就是有那么一部分?jǐn)?shù)學(xué)家像“老林”一樣，窮盡幾十年來研究這個(gè)問題?？赡苓@就是數(shù)學(xué)的魅力吧！

?OK! OK! 文章到此結(jié)束了。今天寫這篇文章并不是想要真正探討這個(gè)學(xué)術(shù)問題，一是為了緩解一下學(xué)習(xí)壓力(畢竟最近一直學(xué)習(xí)Java)，二是為了滿足一下自己和大家的求知欲 (好奇心)。最后再次推薦一下這部劇——“天才基本法”，真的好看！

回到目錄…

到了這里，關(guān)于什么是P = NP?問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！