演算法中的玄學 - NP 問題

科學的盡頭是玄學，而演算法的盡頭，肯定就是 NP 問題了。

寫了幾十年程式的非科班老程序員這陣子回頭讀演算法，花了點時間搞懂(自以為?)演算法中的玄學 - NP 問題。

許多演算法複雜度討論，最後都指向一個終極議題 - NP 問題，甚至還會升級到哲學層次，主張「P=NP 是否成立」將決定我們所處世界的真相：

If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.

如果 P = NP，那麼世界將會與我們以為的截然不同。「跳躍式創意」將不再有什麼了不起，解決問題與鑑別解答間將不存在根本差異。 能欣賞交響樂的人都能成為莫札特；理解逐步論證的人都能像高斯；每個看得懂投資策略的人都是股神巴菲特。

以上是複雜度理論專家 Scott Aaronson 為 NP 問題所下的註腳。

前陣子研究 NP 問題，費了不少心思終於理解 Scott Aaronson 的那段鬼話是什麼意思，得到小小成就感。

NP 問題不像排序、配對... 等具體可想像的演算法題目，它涉及數學推導及抽象概念，無法透過程式碼實際驗證，故理解很需要想像力。學習過程我產生了無數疑問，靠參考資料消化整理，一一找出說服自己的解釋，總算是梳理出一套邏輯通順的說法(至少能讓我買單)，為記錄這段艱辛歷程，這篇將用 QA 方式整理我的理解與心得，希望對也在努力搞懂 NP 問題的同學有所幫助。

以下會假設大家對演算法的時間複雜度、圖靈機已有粗淺認識，從這個基礎出發。下面是我這次主要參考的文章，推薦大家可先讀完再回頭看我的整理。

• 資訊之芽算法班 Complexity 投影片
• 為什麼要區分演算法的 NP 問題 by 李耕銘
• 輕鬆談演算法的複雜度分界：什麼是P, NP, NP-Complete, NP-Hard問題 by YC

1. P 問題的 P 是什麼？

   P 問題的 P 代表 Polynominal，指多項式時間。

   演算法有快有慢，有些不論資料筆數多寡都能很快算出答案，有些則是資料筆數一多便要算到地老天荒，海枯石爛都等不到答案。資訊科學習慣「用大 O 符號」表示運算時間或耗用記憶體與資料筆數關係，計算時間與資料筆數的關係則稱為時間複雜度：

   • O(1) - 運算時間固定，不受資料筆數影響
   • O(n) - 運算時間與資料筆數 n 成正比
   • O(log n) - 運算時間與 log n 成正比
   • O(n²) - 運算時間與 n 平方成正比
   • O(2ⁿ) - 運算時間與 2 的 n 次方成正比
   • O(n!) - 運算時間與 n 階乘成正比

   
   圖表來源：初學者學演算法｜談什麼是演算法和時間複雜度 by 胡程維

   超過 n 的多次方，時間便會呈指數性成長，一般被認定無法求解。當時間呈現指數性成長，n 也不用大，隨便抓個 n = 100，2¹⁰⁰ 這個數字可能大到超乎你想像，地球上所有原子的總數也不過 2 的 50 次方，2 的 100 次方到地球毀滅都算不完。

   若時間複雜度可用 a * n^k + b * n^k-1 + ... 這種多項式表示，一般被認定能在可接受的時間內算出答案的，小於等於多項式時間複雜度的問題，稱為 P 問題，被視為可解的問題。

   因此 O(1)、O(n)、O(log n)、O(n²) 屬於 P 問題，O(2ⁿ) 及 O(n!) 不屬於 P 問題。

2. 那麼，所以 NP 問題 NP 是指 Non-Polynominal 嗎？

   錯! NP 問題是 Non-deterministic Poloynominal 的縮寫，至於什麼是 Non-Deterministic 得先了解圖靈機，NP 源自 Non-Deterministic Turing Machine，非確定性圖靈機(NTM)，以下就來說說 NTM 是啥。

3. Non-Deterministic Turing Machine 非確定性圖靈機 (NTM) 是什麼鬼？

   圖靈機由英國數學家艾倫·圖靈在 1936 年提出，一部可將人類計算行為抽象化的數理邏輯機，心是一台能實現任何有限邏輯數學計算的終極邏輯機器。(圖靈就是電影模仿遊戲裡的天才數學家，當今資訊科學界的諾貝爾獎 - 圖靈獎 也是以他命名)

   圖靈機的概念是有個讀寫頭(HEAD)在無限長的紙帶(TAPE)上移動，可讀取、抹除及寫入符號(SYMBOL)，並可儲存狀態(STATE)，至於移動方向、是否抹除或寫入符號則是由一套指令規則(TABLE)依狀態決定。這個架構如同當今電腦的縮影，有輸入輸出，有記憶體記錄狀態，程式邏輯即指令規則表，能實現各種複雜邏輯。同理，這個抽象的圖靈機，理論上可實現人類想得出來的所有演算法。

   
   圖靈機想像圖(來源：維基百科)

   一般來說，圖靈機的規則在特定狀態的下一步行為是確定的，例如：狀態為 0 時往左移、為 1 時往右移，我們用的電腦即是用這種方式運作，稱之為確定性圖靈機(Deterministic Turing Mahcine，DTM)。假設還有另一種更厲害的圖靈機，當前狀態的下一步動作可以是不確定的，狀態 0 時讀寫頭可以向左也可以向右移動，像在每個分叉點不斷分裂出平行宇宙，靠著「無限並行」的計算能力，能在多條計算路徑中同時尋找正確的解答，這種神奇的圖靈機稱之為非確定性圖靈機(Non-Deterministic Turing Machine, NTM)。

   NTM 可以被想像是一台神奇機器，我們用的電腦即便能平行運算也苦哈哈跑過所有的路徑找答案；NTM 就不同了，其神奇之處在於它能一次猜中正確路徑得到結果，只要沒有無窮迴圈，再複雜演算法也可以很快得到答案。因此，只要我們有能力驗證結果是否正確，再複雜的演算法都可用 NTM 求解。想當然爾，NTM 在真實世界並不存在，至少現在還沒出現。

4. 所以求解跟驗證的時間複雜度會不一樣？

   是的，有許多問題的特色是求解困難，但驗證很快。經典例子像是數獨，要花很多力氣推敲每個格子該填什麼數字，但填的數字對不對卻很好檢查。又像是拼圖，拼完一萬片拼圖要花可觀的時間，但有沒拼錯看一眼就知道了：
   

5. 扯了這麼多，NP 問題到底是什麼？

   我們知道有很多問題很難求解但驗證很快，比如求解演算法時間複雜度是 O(2ⁿ)，但驗證可在多項式時間內完成，這類問題在現實世界原則上是算不出來的(需要指數時間)。但假設我們手上有神奇的 NTM 非確定型圖靈機，當求解過程遇到可以走 A 流程也可以走 B 流程，NTM 一律用猜的且總能幸運猜對跑對流程算出結果，加上能多項式時間內驗證答案正確，如此就一定可以解出答案。

   這種不一定能在多項式時間求解，但一定可以在多項式時間內驗證答案的問題，若有 Non-deterministic Turing Machine 在手就一定能在多項式時間內解出答案，符合此條件的問題就是所謂的 NP 問題。(Non-deterministic Polynominal Problem)

6. 若不論運算時間長短，所有問題都是有解的嗎？

   圖靈機理論中的問題可區分為 Recognizable(可識別) 跟 Decidable(可判定) 兩種，Recognizable 問題是指圖靈機在提供輸入開始運算後，可能算完停機得到結果，也可能陷入無窮迴圈永遠停不下來。而 Decidable 問題則是一定會算到停機得到結果。對於 Recognizable 問題，就算用 NTM 也不保證能算出答案。而 Decidable 問題則一定能得到結果，只在時間長短。

7. 演算法中的 Reduction 歸約是什麼？

   應用演算法解問題時， Reduction 歸約是很好用的技巧，其概念是「將 B 問題當成 A 問題的一種特例，直接使用 A 問題的演算法求解」。想像在解數學題時發現某道題目很難但跟之前做過的某種題目很像，便可將題目轉換成那道會解的題目求解。例如我們已學會除法求餘數，之後遇到判斷偶數時，將其轉換成除以 2 檢查餘數是否為零。這種「把未知難題轉換成已知問題」的技巧，在電腦科學中即所謂 Reduction（歸約）。

   若問題 B 可轉成問題 A 求解(B ≤ A)，問題 C 也可以轉成問題 A 求解(C ≤ A)，意味問題 A 的演算法必須要涵蓋 B、C 兩種案例，故其複雜度一定比 B、C 問題為高。我們會說 A 問題會比 B、C 問題難，若有能力解掉 A 問題，就一定也能解掉 B、C 問題。

   以電腦邏輯電路為例，所有的邏輯都可以用 AND、OR、NOT 閘表示，故所有運算邏輯都可以 Reduce (歸約)成 AND/OR/NOT 閘的組合，故先解決用 AND/OR/NOT 邏輯閘實現運算這個難題，便能解決任何邏輯線路問題。

8. NP-Hard、NP-Complete 問題又是什麼？

   搞懂 Reduction，就可以解釋 NP-Complete 跟 NP-Hard。
   前面說到，若一堆問題都可歸約成某個最難的問題，那我們只要找出這個最難問題的解法，就可一次解掉一堆問題。一堆 NP 問題歸約到的最難問題，就稱為 NP-Complete 問題。

   Cook 在 1971 年證明出第一個 NP-Complete 問題 - SAT 問題，而 1972 年 Karp 則再證明了 21 個令人聞風喪膽的組合數學與圖論問題也是 NP-Complete 問題。參考

   由於所有 NP-complete 問題最終都可以在多項式時間內被轉換成 SAT 問題(就像再複雜的邏輯運算都能轉成 AND/OR/NOT 組合)，這就意味著，只要我們能在多項式時間內解決一個 NP-Complete 問題，就代表所有 NP-Complete 問題都能在多項式時間解決。

   除了 NP 問題，世界上還存在一些非 NP 問題(無法在多項式時間內驗證)，所有 NP 問題與非 NP 問題能在多項式時間內歸約的最難問題，我們稱之為 NP-Hard 問題。

9. 所有談 NP 問題的文章都出現一張像籃球禁區的圖，它在說啥？

   
   有了前述的知識，我們終於能看懂這張圖了。先看左邊的圖來個自我測驗，該圖是全世界所有問題的分類及關聯，各區域的定義分別為：

   • [1] P 問題 - 能在多項式時間求解的問題
   • [2] NP 問題 - 不一定能多項式時間內求解，但可在多項式時間內驗證，用 NTM 非確定型圖靈機一定能解
   • [3] NP-Complete 問題(NPC) - NP 問題可在多項式時間歸約成的最難問題，若能在多項式時間內解掉任一個，代表所有 NPC 問題都能在多項式時間內求解
   • [4] NP-Hard 問題(NPH) - NP 或非 NP 問題可在多項式時間歸約成的最難問題
   • [5] 非 NP 問題 - 無法在多項式時間內驗證的問題

   所有的 P 問題一定是 NP 問題，NP-Hard 與 NP 的交集是 NP-Complete 問題。而右邊的圖則關乎你我是否能成為莫札特、高斯跟股神巴菲特(大部人應該只在乎最後一個 XD)，就是所謂 P = NP 猜想。

10. P = NP 還是 P ≠ NP 為什麼這麼重要？

    整理前面提到的幾項重點：

    • 所有 NP 問題可以歸約成 NP-Complete (NPC) 問題
    • 所有 NPC 問題又可以歸約成任一個 NPC 問題
    • 歸約對象的問題的解法可以求解原問題

    由此推論：只要任一個 NPC 問題證明能在多項式時間內解開，代表所有 NPC 問題都能歸約成它也在多項式時間內解開；若 NPC 問題都能在多項式時間內解開，則全天下的 NP 問題便能歸約成這些 NPC 問題在多項式時間內解開；一旦 NP 問題能在多項式時間內解開，NP 問題就變成了 P 問題，P = NP，世上所有 NP 問題都能在多項式時間內解開。

    換句話說，若 NPC 問題有解，代表 P = NP，我們對這個世界的理解就改觀了。只要有能力(在多項式時間內)鑑別答案正確與否，確認它是 NP 問題，就一定靠著歸約成 NPC 問題在多項式時間內得到解答。這就是文章開頭 Scott Aaronson 那段話的意涵，聽得懂交響樂就是莫札特，看得出投資策略好壞就能成為巴菲特。

11. 那麼，P = NP 嗎？

    這個問題目前還沒有定論，找出答案的人可以得到 100 萬美金。
    P = NP 是 2000 年美國克雷數學研究所懸賞的千禧年七大數學難題之一，解開任何一題可獲得 100 萬美金的獎金。

    前面說過 NPC 問題可歸約成其他 NPC 問題，所以只要能證明已知的 NPC 問題中的任一題可在多項式時間內解開，就等同證明 P = NP，百萬獎金入袋。(註：七大難題目前僅有龐加莱猜想被解開，但作者帥氣地拒絕領獎)
    不過，也沒有人能證明 P ≠ NP，故目前人類還不知道這個問題的答案。

    2002 年起，William Gasarch 就 P = NP 問題對研究人員進行了三次民意調查。相信 P ≠ NP 的人由 2012 83% 增加到 2019 的 88%，而 99% 的專家認為 P ≠ NP。參考

12. 假如有一天被證明 P = NP，會發生什麼事？

    如前面所提，當 P = NP，代表我們以為的 NP 問題其實都可以被解出來，人類將有能力找出生產排程、投資組合、財務預測等難題的絕對最佳解，世界經濟將會被改寫。
    但先別高興得太早，在 P = NP 帶來的危機面對，這些效益不值一提。

    最顯而易見的危機是現代所有的資安防護機制將會瓦解，有史以來密碼學的加密、簽章之所以無法破解，都基於破解演算法為 NP 問題的假設。一旦 P = NP，代表所有密碼學演算法都能在多項式時間內被破解，則沒有任何加密是安全的，數位簽名都可以被偽造，資訊安全瞬間歸零。感覺 P = NP 會導致世界末日啊! 不過，目前 99% 專家都相信 P ≠ NP，是不用杞人憂天啦。