世界是否有捷徑？

路西

2000年初，美國克雷數學研究所選定了7個“千禧年大獎難題”：NP完全問題、霍奇猜想、龐加萊猜想、黎曼猜想、楊-米爾斯存在性和質量缺口、納衛爾-斯托克方程和BSD猜想。NP完全問題位于這個數學難題清單的第一項，是計算機科學領域最大的難題，也可能是所有數學問題中最難的一項。P完全問題即P=NP？問題由史蒂芬·庫克在1971首次提出，它是七大千禧年大獎問題中最年輕的問題，同時也是最好理解的一個。

什么是P和NP？

在我們的生活中，有些數學問題可以很快地解決，比如買東西結賬;但是有些數學問題卻要花大量的時間去解決，比如下象棋。隨著數學和計算機科學的發展，針對于部分比較難解決的數學問題，人們想出了更好的算法，所以解決它們需要的時間就變少了。將問題分為快速解決和慢速解決兩種的話，加減乘除是可以快速解決的問題，而下象棋是慢速解決的問題，當然還有許多的問題，我們不清楚應該將它們分于哪一類。于是我們就用了包含P與NP的更精準的定義去分類這些數學問題。

P問題包含所有可以被計算機程序快速解決的問題，比如加減乘除。NP問題是指如果給出一組問題的答案，你至少可以在合理的時間里檢查這個答案是否正確。例如給定一個數41607317，如果對這個較大數做質因數分解，是有些難度的。但是如果給出一個可能的答案比如8699和4783，你可以通過將兩個數相乘對比原來的大數，很快地得出8699和4783這兩個數是正確答案。世界上有很多的問題，我們很難去找到它的答案，但是如果給出了答案，驗證這個答案是否正確卻是相對簡單的。例如，做出數獨的答案，可以很簡單的驗證結果的正誤，但是我們至今沒有找到一個可以完美解決所有數獨問題的最優途徑（想象1000×1000級的數獨，而不是9×9的），做數獨往往還是用試數的方法（即枚舉法）。

毫無疑問，NP問題包含P問題，因為對于P問題只需按部就班地算出問題的答案進行對比就可以了。

最難的NP問題與NP的外界

所有人都認為NP所包含的問題比P所包含的問題要多，即使有些問題還沒有被發現，當然現在還沒有人能夠證明這一點。數學家發現很多NP問題其實是互通的，比如數獨問題的本質和蛋白質折疊問題是一樣的，如果你能找到解決數獨問題的最優算法，蛋白質折疊這一21世紀最重要的生物學問題也將迎刃而解。數獨和蛋白質折疊問題屬于NP中的一個下屬分類NPC（NP-Complete）問題。NPC問題是NP中最難的一部分，這些問題的復雜性（解決問題需要的時間和空間）與整個類的復雜性相關聯，如果我們能快速解決某一NPC問題，那么所有的NP問題都能快速解開。

NP問題需要花很長的時間去求解，但是很容易驗證結果的正確性。在NP之外，還存在著一些問題，驗證這些問題的結果甚至都是不可能的，例如，我們很難判斷象棋中的某一步是不是最好的。還有Co-NP問題，與NP問題不同的是，Co-NP問題可以在合理的時間內很容易地排出錯誤解，而不是驗證正確解。Co-NP問題與NP問題是否是互通的，我們也不得而知。除此之外，還有非常多的問題分類，每一個分類都需要花費大量的時間去解釋。

P=NP？

NP是舉足輕重的，因為它包含了一些非常重要的問題，比如：旅行商問題（給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路），電路設計問題和數據庫問題等，如果這些問題得到解決，我們的生活將會有翻天覆地的變化。因此，數學家們一直積極地解決各種數學問題。在這個努力的過程中，我們有時會幸運地發現一些NP問題實際上是P問題，我們就找到了解決這個問題的捷徑，同時仍有很多的NP問題還不能被歸類為P。科學家開始思考：NP中的所有問題最終都會變成P問題嗎？還是有些NP問題就是比P問題難解決的多？這就是著名的P=NP？問題。

解決P=NP猜想的方法有兩種，一種是找到NP問題的解決算法，那么所有的NP問題就都可以解決了;另一種就是從數學理論上證明這樣的算法不存在。但是現在的很多數學家在證明這一問題上存在誤區，他們往往假設一種可能的解決算法，然后設法證明這種算法的錯誤性或不存在。實際上證明P=NP問題本身就是NP問題之一，這讓我們感到更加的困惑。

如果P=NP，那么我們就能找到簡單的解決問題的方法，換言之，就是人類在解決復雜問題的時候是有捷徑的。計算機一下子就可以變得非常的“聰明”，可以在十分混亂的局面中，快速找到一個捷徑。當獲知了所有的信息以后，計算機可以在極短的時間里，對證券市場、天氣、球賽結果做出非常準確的預測;計算機能夠輕松找到一個算法，來知道藝術作品是如何直擊人心的，于是計算機可以為每個人定制出他最喜愛的音樂、藝術作品。與此同時，人工智能可以快速的自我優化，意味著人類的末日可能到來了;密碼學的基礎也很容易就會被破解，我們每個人都毫無秘密可言。

P=NP嗎？數學家還沒有答案。