有點燒腦
空調開好
超模君今天重溫了綜藝《百萬富翁》，在想到底有沒有一道題是價值百萬的呢？
答案是有的，他就是著名的「千禧難題」。
千禧年大獎難題(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年，歷經三百多年的歷史才被懷爾斯徹底證明。
同樣，我們對解決這個問題仍然抱有希望。
本文系網易新聞·網易號「各有態度」特色內容
部分資料來源於網絡
轉載請在公眾號中，回復「轉載」
▼▼▼點擊查看數學滿分應有的姿勢▼▼▼
①購買2件打9折，領券最高減10元！
②購買3件以上，私聊小天贈送超模君新書1本！
來來來 你還在等什麼？
▼▼▼
關注「超級數學建模」的模友
一直都在問
超模君怎麼很少
講中小學的數學呢
那麼，現在來了
微信公眾號「少年數學家」
提供豐富的數學課外知識
數學人物、數學趣談、科技與數學
想讓孩子懂得更多有趣的數學
記得關注「少年數學家」