有點燒腦

空調開好

超模君今天重溫了綜藝《百萬富翁》，在想到底有沒有一道題是價值百萬的呢？

答案是有的，他就是著名的“千禧難題”。

千禧年大獎難題(Millennium Prize Problems),又稱世界七大數學難題， 是七個由美國克雷數學研究所(Clay Mathematics Institute,CMI)于2000年5月24日公布的數學猜想。

這些都是極難的問題，其中大多數需要大量的專業知識，甚至光理解題目就很吃力了。

但隻要你解破其中一題即可獲獎金100萬美元，相當于人民币6934900元。

為了照顧下學渣，今天要講的是最容易理解和解釋的一個。

☛ P=NP？

有捷徑？沒有捷徑？

P=NP問題，其實就是在問生活是否存在大量可證明的捷徑。

那麼P和NP到底是什麼？

P代表了這樣一類問題，計算機在解決它們的時候可以有速度非常快的方法。這個速度和計算機硬件無關，僅僅取決于這個解決方法本身的便捷性。NP代表了另一類問題，它們有最優解，但是，其中很多問題，計算機在尋求最優解時，沒有快速的方法，隻能傻傻的、暴力的、嘗試所有可能的組合，然後找到最優解。NP問題中，最難的一類問題，被稱為NPC，也就是NP完全問題。

這個問題有什麼意義嗎？

意義就大大大了！

如果P=NP，則意味着，每一個NP問題都可以轉化成P，也就是每一個難題最終可以變成一個簡單命題，讓計算機快速求解。

如果P≠NP，則意味着，很多NP問題無法簡化成P，也就是計算機隻能很傻很暴力的去求解。

跟我們這些普通的地球人有什麼關系？

如果真的成立了，就意味着人類在解決複雜問題的時候就存在捷徑了！

聽起來好像很厲害的樣子，能具體點嗎？

假如P=NP的世界會怎樣

試想下一個充滿求解捷徑的世界會是怎麼樣？

舉一個場景，随着互聯網的發展，RSA加密協議被廣泛應用于各行各業，特别是電子商務。

RSA是什麼？

RSA是目前最有影響力和最常用的公鑰加密算法，基于計算乘積容易，分解因數則很難的數論事實，它能夠抵抗到目前為止已知的絕大多數密碼攻擊，已被ISO推薦為公鑰數據加密标準。

就是這麼一個目前安全系數最高的的協議，在P=NP的世界裡将會被輕易破解。

RSA加密協議的核心——因數分解問題将變得能被高效地計算，我們可以找到幾百萬位數的質數因子。因此，P=NP将讓RSA協議失效，所有基于公鑰加密系統的協議也都将失效。

再來個栗子：蛋白質折疊問題也将會迎刃而解。當你需要進行癌症治療時，不會是無法治愈的結果了。

科普一下，蛋白質會由所含氨基酸殘基的親水性、疏水性、帶正電、帶負電等特性通過殘基間的相互作用而折疊成一立體的三級結構。

就是說蛋白質折疊涉及到内外部的不同因子的組合，導緻其預測結構的可能性非常的多。因此，我們現階段的難題就在于無法在短時間中從氨基酸序列計算出蛋白質結構，甚至無法得到準确的三維結構。

然而在P=NP的世界裡，我們可以通過确切的程式算法，準确無誤地制造出特定的蛋白質，其折疊方式不僅能有效地餓死癌細胞，而且對正常細胞沒有任何影響。

另外，空當接龍、掃雷、數獨等一些經典遊戲也因為算法而在很大程度上變得索然無味。甚至說，當你在圍棋對弈的時候，就已經知道正确的第一手，按照算法寫好的劇本一直領先。

總之，在P=NP下，許多重要的未解之謎都可以被算法快速的KO了，特别是生物學和治療癌症、商業和經濟、破解網路金融的加密等等的難題。

最終有人可以證明嗎？

但關于P和NP問題，目前還沒有被證明。

但大多數人的觀點是認為P≠NP。

因為當我們面臨一個NP完全問題時，不可能找到一個在所有情況下都能解決該問題的算法。此時就要借助于其他方法，如近似計算、啟發式方法、暴力破解等方法的組合，然後去盡可能的争取最好的結果。

然而證明P≠NP并非易事。你需要證明不存在有效的算法能解決團問題或任何其他的NP完全問題，這些算法除了包括現有的還包括将來發明的。

雖然如此，但就像費馬大定理，從17世紀到1995年，曆經三百多年的曆史才被懷爾斯徹底證明。

同樣，我們對解決這個問題仍然抱有希望。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!