【為什麼要區分演算法的 NP 問題】

前言

目前會去區分P、NP、NPC、NP-hard的演算法課程似乎越來越來少，因為除了走學術研究或考研究所真的不太會用到，不如多刷幾題 LeetCode 對人生根職涯還比較實際，舉一段演算法筆記中的註腳：

台灣的演算法課程，都是直接抄舊書，特別強調 NP-complete ，特別強調問題之間的轉換。不過職場上幾乎不會用到這些知識。學術上要解決 P = NP 問題，也不會用到這些知識。

現在比較新的教學資料，都是直接介紹多項式時間和指數時間的差異，而不是去介紹 P 、 NP 、 NP-complete 、 NP-hard 到底誰包含誰。

不過個人覺得還是可以把 NP 問題當作故事來讀讀，去看看以前那些學者遇到問題時是怎麼逐步嘗試解決的，而且野心還很大，想要證明「所有」的演算法問題只要能被簡單驗證就能被簡單算出來。

至於要去區分 P、NP、NPC、NP-hard，個人也覺得除非你要考研究所不然就算了吧。另外，內文如果有發現怪怪的，那一定是我錯了，再麻煩留言勘誤，感謝。

*這裡的簡單指的是在多項式時間複雜度內。

電腦科學中的「問題」可以分成兩種

1. 決策問題 (Decision Problem)

只需要回答是或不是，若回答是，須給出能滿足要求的解，若回答不是，須給出相對應的證明。

Ex：123 是不是質數？

2. 最佳化問題 (Optimization Problem)

須從有限的答案中選出其中最佳的解，通常最佳化問題比決策問題難。

Ex：最佳排班方式、最短路徑問題

最佳化問題可以轉成決策問題

若給予一個最佳化問題，我們均可轉換成與之對應的決策問題，稱為這個最佳化問題的決策版本。

Ex：最短路徑問題的轉換

• 最佳化問題：
  給定由頂點與邊構成的圖，試著從中找出兩點間的最短路徑
• 決策問題：
  給定由頂點與邊構成的圖，以及一個常數 C，能否找出一路徑使兩點間的最短路徑 <Ｃ？

但決策問題不一定可以轉換成與對應的最佳化問題，所以稍後提到的 NP 問題主要在分析的都是決策問題。

如何描述問題的難度？

你會怎麼描述問題的難度？

今天給你一個問題，你想要跟對方說這問題很難，你會試著怎麼描述？

• 這問題好難喔，沒有計算機我不會。
• 這問題好難喔，不管有沒有計算機我都不會。
• 這問題好難喔，不只有我，大家都不會。

很明顯的這些講法都不夠精確，而在電腦科學中我們也迫切需要有一個方法去區分問題是困難或簡單的，而在電腦科學中，我們會以該問題是否有一個多項式時間複雜度的解法來定義難或不難。

等等，甚麼是多項式時間複雜度？

回憶一下國中老師所教的多項式還有 Big-O，也就是多項式的時間複雜度可以表達成下列數學式：

也就是如果可以把演算法的複雜度寫成 O(n^k)的話，那這個問題就有多項式時間內的複雜度，不能被表達成 O(n^k)的時間複雜度則為非多項式時間。

舉幾個例子：

1. 2^n →非多項式時間複雜度
2. 1.5^n →非多項式時間複雜度
3. n³ →多項式時間複雜度
4. n log n→多項式時間複雜度

之所以會這樣定義可以看看下面的表格，當演算法的時間複雜度在 2^n 以上時，若資料量超過 100 筆，就幾乎不可能用電腦算出答案。順帶一提，全世界的原子個數總數頂多也才 10⁸⁰ 次方個。

還有表格中右下角的 X 是因為我丟到 Google 搜尋裡搜不出答案，可見它到底有多大，連 Google 都沒辦法告訴你的大。

但其實還有一點很重要：若目前還找不到多項式時間的解法，也無法保證未來就一定找不到，並無法由此證明此問題是難解的。現在找不到，不代表以後找不到。

根據問題的難度區分成以下四種

1. P (Polynomial Time)：存在多項式時間複雜度的演算法來解決問題
2. NP (Nondeterministic Polynomial Time) ：存在多項式時間複雜度的演算法來驗證問題的解答是否正確
3. NP-hard：所有的 NP 問題都可以化成 NP-hard 問題，而且這類問題還沒有找到多項式時間複雜度的算法，每一組解能否在多項式時間的算法內被驗證則不一定。
4. NP-complete(NPC)：所有的 NP 問題都可以化成 NP-complete 問題，而且這類問題目前還沒有找到多項式時間複雜度的算法，但每一組解都可以被多項式時間的算法驗證，因此 NPC = NP ∩ NP-hard

P 與 NP 問題

解決與驗證

要解決問題或是驗證答案往往是不一樣的難度，比說排序，學過演算法的人都會知道目前排序的複雜度是：O(n logn)，但驗證一個數列是否為排序好的只需要 O(n) 就可以辦到。

驗證答案的難度 ≤ 算出答案的難度

所以根據運算與驗證答案的難度，我們可以根據其是否能在多項式時間中被解決或驗證來區分成 P 問題與 NP 問題。

P 問題

P 問題 (Polynomial Time) 指的是該問題可以在最壞狀況 (Worst-Case) 下被多項式時間內的算法解決。簡單來說就是：Easy to find.

NP 問題

NP 問題代表的是：不確定(可能可以，也可能不可以)在多項式時間是否可被解決，但確定可以在最壞狀況 (Worst-Case) 下被多項式時間內的算法驗證。

在 Clay Mathematics Institute 裏頭有舉一個 NP 問題的例子：

給定 400 位學生與一個有 100 個床位的宿舍，但同時有一份不相容的名單，名單上的學生兩兩成對，名單上的每一對學生都不能同時住宿在宿舍中，請給定一個分配宿舍的方式。

此為典型的 NP 問題，因為給定一解，我們可以很容易地透過依序檢查該名單上的學生是否同時存在於解中來驗證該解是否成立。但卻沒有辦法給出必定能在多項式時間複雜度中解決的算法。

注意 NP 並不是 not polynomial time，這是常見的誤解，簡單來說 NP 問題就是：Easy to check.

另外還有一點就是：P 問題一定是 NP 問題 (P ⊆ NP)，因為一旦問題可以在多項式時間內被解決，它就可以在多項式時間內被驗證，解決問題的方式本身就可以拿來驗證。

P 問題跟 NP問題一樣嗎？

• 如果能夠證明 P = NP，也就是所有能在多項式時間內被驗證的問題，都可以在多項式時間內被解決，這會是世紀大發現！
• 如果能夠證明 P ≠ NP，有些能在多項式時間內被驗證的問題，註定無法在多項式時間內被解決，這同樣會是世紀大發現！

那究竟 P 問題跟 NP 問題一不一樣呢？

千禧年世紀難題

因為 P 問題是否等於 NP 問題在電腦科學裡實在是太重要了，不管是證明 P = NP 或 P ≠ NP ，都對推進演算法的發展有莫大的幫助，所以它甚至被列在七個千禧年世紀大難題之首。下面我借用維基百科來解釋千禧年世紀難題。

千禧年大獎難題（英語：Millennium Prize Problems）是七個由美國克雷數學研究所（Clay Mathematics Institute，CMI）於2000年5月24日公布的數學難題，解題總獎金700萬美元。根據克雷數學研究所制定的規則，這一系列挑戰不限時間，題解必須發表在國際知名的出版物上，並經過各方驗證，只要通過兩年驗證期和專家小組審核，每解破一題可獲獎金100萬美元

1. P/NP問題
2. 霍奇猜想
3. 黎曼猜想
4. 楊-米爾斯存在性與質量間
5. 隙納維-斯托克斯存在性與光滑性
6. 貝赫和斯維訥通-戴爾猜想
7. 龐加萊猜想 (已被解決)

只要你能夠證明 P 跟 NP 是一樣或不一樣，恭喜你，100萬美金入袋！！！
(雖然 100萬美金還是買不起台北的房子......)

歸約 (Reduction)

再繼續談 NP-hard 跟 NP-complete 前，我們必須先看看歸約(Reduction)。

歸約(Reduction)

歸約的定義是把某個計算問題A 轉換為另一個計算問題 B，可以寫成

A ≤ B

可以想像成「問題B 至少跟問題A 一樣難」，有問題B 的多項式時間解法，那問題A 同樣有多項式時間解法，比方說：

Ex：把判斷是否是質數的問題(A)，轉成找出所有因數問題(B)

• 如找出所有因數有多項式時間解，判斷是否是質數亦有多項式時間解
• 如判斷是否是質數無多項式時間解，則找出所有因數亦無多項式時間解

就像是我之前寫過搬磚套利問題可以轉成圖論中的負環問題一樣，不同的問題透過轉換後可以變成同一個問題。

(但歸約本身也是問題，所以這裡所說的歸約都必須在多項式時間內達成)

為什麼要進行歸約

那為什麼要進行歸約呢？因為演算法的問題實在太多，如果能把所有 NP 問題歸約成單一問題，並證明該問題其實是一個 P 問題，就代表所有的 NP 問題都可以被當成 P 問題！

Ex：世界上的問題如果都可以歸究給貧富差距，那麼我們只要解決貧富差距那世界上就沒有問題了！

我很喜歡用下面一張圖來解釋為什麼要進行歸約，左側可以想像成有一大堆等待被解決的演算法問題，透過歸約 (reduction) 我們可以把它變成單一問題 (NP-hard)，只要能夠解決右邊這個單一問題，那麼代表左側的所有問題都能夠迎刃而解，夠不夠吸引人？

NP-hard 問題

另一點就是：歸約化具備傳遞性，也就是如果問題A 可歸約為問題B，問題B 可歸約為問題C，那麼問題A 便可歸約為問題C，透過傳遞性連結眾多 NP 類問題，最終就會出現 NP-hard 問題。
(若此問題同時是 NP 問題，則為後面會談到的 NPC 問題)

也就是所有的 NP 問題最終可以歸約化到 NP-hard 問題

NP ≤ NP-hard

NP-complete 問題

之所以目前 P=NP 或 P ≠ NP 的問題還沒有被證明，而且普遍的共識還傾向是 P=NP 問題應不成立，也就是至少有一個 NP 的問題是注定無法在多項式時間內解決的。

至於為什麼會有這個共識？乃是因為 NP-complete (NPC) 問題的發現。

NPC 的全名是 = Non-deterministic Polynomial Complete problem，也就是大量的 NP 問題可以經過歸約後發現的終極 NP 問題，NPC 問題是 NP類中「最難」的問題，跟 NP-hard 不一樣的是 NPC 本身也是 NP 問題，也就是 NPC 問題本身就可以在多項式時間內被驗證。

用歸約來解釋 NPC

這裡我借用 CMU 的解釋&圖片來定義 NPC 問題：

• Y 是 NP 問題
• 對所有的 NP 問題 Y ，都可以歸約成另一 NP 問題 X，即 Y ≤ X
• 則代表問題 X 是NP問題中最難的 :(

Ref: CMU

NPC 問題一定是 NP問題

• 跟 NP-hard 問題不同之處， NP-hard 問題不一定是 NP 問題，所以 NPC 問題是 NP-hard 問題中的特例。
• 也因此 NP-hard 問題通常比 NP-complete 問題更難。
• 故 NP-hard 不一定完全包含NP，兩者的交集為NPC

Cook-Levin理論

1971年 Stephen A. Cook提出了Cook-Levin理論：

任一 NP 決策問題都可在多項式時間內轉成同一個問題「布林方程式是否存在解」

也就是所有 NP 問題都能夠殊途同歸到「布林方程式是否存在解」，只要你能在多項式時間內解決「布林方程式是否存在解」，你就能在多項式時間內解決所有 NP 決策問題，藉此證明 P=NP，100萬鎂入袋！

NPC 問題小結

可以說 NPC 問題就是 NP 問題裡的終極 Boss，只要能在多項式時間內解決 NPC 問題，就能證明所有 NP 問題同樣可以在多項式時間內被解決，也就是證明 P=NP 的過程中不再需要證明所有 NP 問題都是 P 問題，而只需要證明其中一個 NPC 問題就是 P 問題。

而目前已經找出上百個 NPC 問題，只要你能夠在多項式時間內解決其中任何一個 NPC 問題，恭喜，100萬美金就是屬於你的了。

總結

1. P (Polynomial Time)
   有簡單的解法
2. NP (Nondeterministic Polynomial Time)
   有簡單的驗證方法
3. NP-hard
   可以把所有 NP 問題歸約成 NP-hard 問題，但這些問題還沒有找到簡單的解法與驗證法。
4. NP-complete(NPC)
   可以把所有 NP 問題歸約成具 NP 性質的 NPC 問題，這些問題雖然還沒有找到簡單的解法，但已經有找到簡單的驗證方法，也就是 NPC 問題是 NP問題與 NP-hard 問題的交集。

(這裡的簡單代表的是可以在多項式時間內被解決。)

• 幾乎所有惱人的決策問題都是 NP 問題
• 這些問題中，可以找到多項式解的叫做 P 問題
• 這些問題中，可以找到多項式算法來驗證解的正確性的叫做 NP 問題
• 我們試圖透過歸約把眾多問題歸約成單一問題，只要能解決這個問題，就能夠解決所有難題
• 但還有一大堆問題目前還找不到多項式時間解
• 宇宙很大，人的所知真的很渺小

最後來看個新聞

https://www.ptt.cc/bbs/Gossiping/M.1618235350.A.604.html

應該可以看懂文章內在表達甚麼吧？

不過因數分解還沒證明是 NPC 問題，所以即便如內文所說真被證明為 P 問題，還是沒有辦法證明 P=NP。

工商服務

這是我開的粉專，覺得有幫助的話可以幫我點個讚，另外我在台大訓練班也有開演算法課程，參考書目是我自己寫的演算法生存指南，有興趣的話可以賞個光。

粉專連結：http://bit.ly/3evM7pk
台大訓練班：https://bit.ly/3mK54c0
演算法生存指南：bit.ly/3HHlTkb