P＝NP？這世界真有捷徑？

在《嫌疑人X的獻身》中，石神和湯川討論，解決一個命題和判斷一個命題是否正確，哪個更難。討論中，他們提到了P≠ NP的證明。這是一個困擾了不僅僅是計算機科學家，也包括數學家、經濟學家、甚至哲學家以久的問題。同時，P/NP是7個千禧年數學難題之一，足見其重要性和難度之大。

....

不過，P與NP這個命題為何如此重要？P與NP分別是什麼含義？我們普通小白到底能弄懂嗎？

《可能與不可能的邊界：P/NP問題趣史》就嘗試用科普的筆法來講述P/NP歷史、淵源和含義。不過，菲菲認為，要完全理解這本書，還是需要一點點計算機思維、人工智慧演算法常識，甚至一點點數學基礎的。否則，可能會出現，能理解作者說的每一個字、看得懂每一段話，卻不懂背後邏輯關係的「尷尬局面」（回憶一下英語閱讀考試的感受...）。

可能與不可能的邊界

說到這裡，大家是不是對P/NP有些恐懼了？其實，這個問題遠沒有它看上去那麼複雜，忽略其背後的數學和計算機科學定義之後，這個問題最終可以簡化為：

這個世界到底有沒有捷徑？

有捷徑？沒有捷徑？

先來解釋一下這個拗口的P和NP是什麼意思。注意，菲菲的解釋是極端極端簡化的，是刻意忽略了背後的數學嚴謹性，讓每個人都能感性上理解這個命題：

P代表了這樣一類問題，計算機在解決它們的時候可以有速度非常快的方法。這個速度和計算機硬體無關，僅僅取決於這個解決方法本身的便捷性。

NP代表了另一類問題，它們有最優解，但是，其中很多問題，計算機在尋求最優解時，沒有快速的方法，甚至，只能傻傻的、暴力的、嘗試所有可能的組合，然後找到最優解。NP問題中，最難的一類問題，被稱為NPC，也就是NP完全問題。

好了，理解了P和NP的定義後，下面就是科學家想要尋找的真理了：

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

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

換而言之，就是，人類在解決複雜問題的時候是否有捷徑？

說到這裡，大家可能還沒有意識到如果P=NP的威力。下面，就來給大家展示一下如果人類找到了世界的捷徑，也就是找到了P=NP的方法後，世界會成為一個怎樣神奇的樣子！

充滿捷徑的神奇世界

大家熟知的證券市場，充滿了各種信息，它們交互作用，讓準確的結果預測變得完全不可能。這是一個典型的混沌系統，如同天氣系統、海洋、足球力學系統一樣。然而，如果P=NP，計算機一下子變得足夠聰明，當獲知了所有信息因子後，計算機竟然可以在極其短時間裡，作出極其準確的預測了！從今往後，人們將可以準確預測天氣、股票、球賽結果...

大家是不是已經在懼怕人工智慧了？是不是已經在擔心機器人將統治我們？但是，比起P=NP 的神奇世界，現在的人工智慧還是很蠢的。如果P=NP，機器人將比現在聰明更多更多更多。從此以後，人工智慧將可以快速的自我優化了！那時候，人類的末日可能真的就來了。

當P=NP，計算機將很容易找到一個演算法，來知道藝術作品是如何直擊人類心靈的，於是，計算機能為每個人訂製出他最喜愛的音樂、藝術作品。什麼，你認為現在的音樂推薦系統已經可以做到？不不不，在那個P=NP的時代，計算機會自我將演算法進化到，鑽進你的內心，成為你的私人訂製作曲家。

如今，人類雖然掌握有人類基因資料庫的數據，但是對其進行數據分析依然是個NP完全問題，這讓科學家即便花費極大運算力氣能找出致病基因，也難以個體化訂製藥品。然而，如果計算機科學家們能夠解開P=NP，從此以後，計算機將能快速為每一位患者訂製出藥物，不管是癌症還是其他和基因有關的疾病。而且為你訂製的藥物，將不會對你產生副作用，而別人使用未必有用。這世間，再無絕症。

P=NP真的可能嗎？

人類至今還沒有找到讓任何NP問題變成P問題的演算法。雖然一些NP問題數學家或者計算機科學家們找到了一些比較快速並且準確率較高的演算法，但是，一個能放之四海而皆準的演算法依然沒有被找到。

那沒有被找到是不是就不存在呢？

如今，絕大部分計算機科學家認為，P≠NP, 也就是，那個能輕易解開世界所有謎題的解並不存在。

同樣，人們從直覺、哲學和宗教來看，也難以相信，有解開世界上所有問題的一把簡單鑰匙。因為，如果這樣的鑰匙真的存在，它大概早已在這個宇宙中存在了。比如，人類可能早已有了萬事萬物看一遍就會的本領，或是某種生物一生下來就不必為了生存而抗爭，因為它們的演算法極其優異，可以在任何環境中以最高效的方式生存下來。

然而，既然人們直覺上相信，這樣的宇宙捷徑並不存在，但是證明其不存在，可不是一件簡單的事情。

證明P≠NP

任何一個能夠證明P≠NP的人，都可以得到百萬美金的獎勵。這麼多年過去，無數的數學家和計算機科學家都努力過，每年都有數以萬計的論文寄往委員會，至今，卻沒有人獲得這筆獎金。

終其原因，正是本文開頭提到的石神和湯川的討論：提出一個猜想（也就是出題）很容易，但要判斷其答案是否正確，非常難。人們猜想了P≠NP，卻非常難以證明。

很多人不理解數學家為什麼會非要「證明」一個猜想。「證明」一個猜想，有非常重要的意義，比如，在P≠NP這個問題上，一旦能夠證明，就意味著，人們不必再花心血去尋找那個超級演算法了，因為，邏輯上，它根本不可能存在！

只是，至今為止，很多試圖證明P≠NP的過程都是錯誤的，人們最常犯的一個錯誤是，他們提出一些可能讓P=NP成立的演算法，然後證明這些演算法並不可能存在，進而得出P≠NP的結論。然而，這個邏輯最大的錯誤在於：這些提出的可能的演算法不成立，不帶表別的演算法不成立。其實，在日常生活中，人們也很容易犯這樣的邏輯錯誤：自己做不到，不等於別人做不到，但人們依然經常認為自己做不到的事情別人也做不到。

那麼，人們最終可以證明P≠NP嗎？

菲菲最近在一個相關論壇看到一段很有趣的評論：每當有P≠NP的證明出來，委員會都需要用NP的時間來判斷這個證明是否正確。也許，要猜想P≠NP是否能被證明，本身就是個NP問題。

不過，鑒於困擾人類幾百年的費馬大定理最終終於被證明了，我們依然應當對P≠NP的證明抱有希望。

另外，說不定，某天真的找到了P=NP的演算法？只是，不知這到底是喜是悲呢？人們如今已經在懷念那個沒有那麼多數據和信息的「慢生活」時代，等宇宙捷徑真的被發現了，生命和生活還能如現在這樣，充滿了懸念、殘缺之美嗎？

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！