P, NP, NPC問題
如果有學習過資料結構或是演算法，相信都對上面的問題不陌生吧。
記得之前還看過有人把這個問題穿上去。
這次就來認識一下在電腦科學中佔有重要地位的問題吧！
Outline:
- 為什麼需要P, NP, NPC？
- 什麼是P, NP, NPC？
- P, NP, NPC 問題之間的關聯性
為什麼需要這些概念？
首先進入我們最重要的題目，為什麼會有這個概念產生？
在計算機的領域界，老師常常說：「同學，要培養解決問題的能力」，但如果今天出現一個問題，怎麼找也找不到一個好方法（時間複雜度比較好的方法）。那我們要怎麼跟老闆或主管證明說這個問題我找不到呢？
這時！！
產生出定義問題難易度的工具，也就是P, NP, NPC的概念就誕生拉！
什麼是P, NP, NPC？
什麼是P問題？
問題可以利用 deterministic algorithm，
並在「多項式時間內」解決。
目前我們所學到的演算法大多屬於P問題，如：sorting。
這裡的Ｐ代表的是Polynomial，問題可以在「多項式時間」內解決解決。
Polynomial time：可以在多項式時間內解決的問題。
Deterministic Algorithm：一般在寫程式的時候，都可以明確地知道下一步要做什麼。Ex: 迴圈跑幾次， 下一個要呼叫哪些函式等等。
然後把可以符合上述條件的問題們都「收集」起來，形成一個集合(Class)，我們稱此集合為P問題。
什麼是ＮＰ問題？
問題可以利用 nondeterministic algorithm，
並在「多項式時間內」解決。
Nondeterministic Algorithm：是一種演算法，但不是我們一般熟知的演算法，它比較像是一個黑箱作業。Input放進程式後，會給出一個 output，但實際上沒有人知道內部的程式是怎麼處理（在這黑箱中沒有人明確地知道下一個步驟是什麼，只知道會出現一個結果），而此演算法的執行時間是可以在 Polynomial Time內解決。
然後把可以符合上述條件的問題，全給他「收集」起來，形成一個集合(Class)，我們統稱此集合為NP問題。
簡單來說：某問題可以在「多項式時間」內解決，只是！使用的演算法是Nondeterministic Algorithm（類似黑箱作業，無法得知裡面的步驟）。
或許現在會想說Nondeterministic到底是什麼？現在來慢慢說明。
什麼是Nondeterministic Algorithm？
一開始認識這個演算法時，真的不懂為什麼要這樣，但時間一久好像也就慢慢接受了。
此演算法包含兩步驟：
- Guessing，猜測 (此步驟屬於Nondeterministic)
- Verification，驗證（此步驟屬於deterministic）
猜測階段(Guessing)
輸入input到某程式中（沒有人知道此程式怎麼撰寫），然後得出一個Output，這樣的過程稱為Guessing，就像是黑箱作業一樣，會產生出答案出(但沒人知道裡面怎麼做)。如果第一次接觸的話，一定會覺得很奇怪，為什麼需要一個「不知道裡面在做什麼的演算法」，這邊簡單解釋一下。
Note：
前面有提到，分成P, NP, NPC是要定義問題的難易度，而nondeterministic的出現，則是為了定義問題的難易度，而產生出的想法。並不代表我們真的可以去「實作」這個演算法，只是將nondeterministic作為一個「定義問題的工具」。
驗證階段(Verification)
驗證剛剛在黑箱作業的output是否正確。
是的話，回答Yes。不是，回答No。
只能回答 Yes 或 No的問題，
通常稱之為「決策問題(Decision Problem)」。
講了這麼多，應該還是不太懂這奇怪的步驟要怎麼使用吧。就讓我用「旅行業務員問題」來說明吧～
旅行業務員問題 ( Traveling Salesperson Problem )
問題說明：
某個業務員要去拜訪 n個城市，而且最後要回到自己出發的那個城市，每個城市只能拜訪一次，不能重複。
問題目標：怎麼樣可以安排最短的（最好的）路徑（順序）。
在看到最好的（最短的），會歸類到「最佳化問題」。
但在剛剛NP的問題的兩個步驟中，步驟二：驗證(Verification)，只能回答Yes/No，隸屬於「決策問題」。那如果給的是「最佳化問題」，要怎麼轉換呢？
＊＊簡單比較一下，最佳化與決策問題的不同＊＊
最佳化問題(Optimize Problem)：怎麼樣可以把路徑（順序）排成最短？
決策問題(Decision Problem)：隨意設一個參數 distance = 5000km，可不可以找到一個順序，總距離小於distance(<5000km)。
如何轉換？(Optimize Problem -> Decision Problem)
引進一個參數，把原問題轉換成 Decision Problem。
Traveling Salesperson變成Decision Problem的版本：
有一個商人要拜訪Ｎ個城市，他找不找得到一個路線「小於5000公里」？
答案：回答只有 Yes / No。（成功完成轉換👏）
那上面講最佳化決策問題的又跟NP問題又有什麼關係？
回到NP（剛剛已經提到Salesperson是隸屬於NP的問題），所以這個評估的流程是怎麼運作的呢？
讓我們從NP的兩個步驟開始：
猜測階段(Guessing)
— 在這個黑箱作業中，可以得到某個路線（序列）。
驗證階段(Verification)
於此問題中，查看兩個條件：
— (1) 針對產生出的那個路線（用字串表示），驗證這個路線，「是否」符合一開始所設的條件（全部的城市拜訪一遍、最後可以回到自己的城市、路途中沒有重複等等）
— (2) 總距離，是否小於某個數字(distance)
其中在驗證步驟中，使用的是 deterministic演算法，也就是有明確指示的程式碼。
如果某問題，可以透過上面兩個步驟得到解答的話，則此問題就會被歸類在 NP的問題。
P, NP, NPC 問題之間的關聯性
再來要提到先前放的圖片，P問題跟NP問題之間的關係為何？
1. 首先可以確定的是，P問題一定包含於NP問題：
為什麼呢？用範例來解釋：
剛剛有提到 Sorting屬於 P問題，Sorting要怎麼利用 NP問題中的兩個步驟去達成呢？
範例說明：現在有 100個數字，利用NP的兩個階段將他做排序。
1. 猜測階段 (Guessing)
— 在黑箱作業中，會產生出一組「序列」(順序)，ex: 1 22 34 56 99 …
2. 驗證階段 (Verification)
— 驗證產生出的「字串」，是否是由小排到大。
是的話，回答 Yes。不是的話，回答 No。
這樣一來，Ｐ問題就成功轉換成ＮＰ問題！！（拍手👏
2. P問題是否會等於NP問題？
這個問題，現在保留的是開放的態度(Open Question)，目前被打上一個大問號？（等講完NPC後，會再多做討論。）
在說明到NPC之前，不能不提到Reductive的概念
什麼是Reducibility？
假設有兩個問題，以個是 x問題，y問題，想要知道 x問題可不可以在「多項式時間內」轉換成 y問題。
如果可以的話：稱之為Reducible。
舉個例子吧：
有一個y方程式和x方程式，現在嘗試要把y轉換成x方程式的形式。
最簡單的做法，會在 y 方程式的最前面加上一個 0x² 就可以變成 x方程式（2次項方程式）（轉換成功！）
如果現在我知道怎麼解2次項方程式的話（也就是我解得出x方程式），同理y方程式也可以順利的解出。
如果可以在「多項式時間」內，把y方程式轉換成x方程式的話，就可以表示成下方的形式。而這樣轉換的想法就稱為Reducibility。
＊＊小p代表，polynomial time時間內。＊＊
什麼是NPC問題：
一般的說法：
歸類於NPC的問題，代表「目前」找不到可以在多項式時間內解決的演算法，但是也沒有人可以證明，此問題「絕對」找不到在多項式時間內的演算法。
正式說法：
我們說一個問題屬於 NPC，他必須滿足下面兩個條件：
1. 它必須是NP
2. 它必須是NP問題裡面，最困難的，也就是NP-HARD。
什麼是NP-HARD？
直接用定義來理解：
假設有一個問題Ｌ自稱它是NP-Hard，則問題Ｌ必定滿足，
說明：NP內可能有很多問題，而裡面的每一個問題(L’)，都可以透過剛剛所提到的「轉換(Reducibility)」，轉換到L問題。
由此可見NP-Hard的問題，即為NP中最難的問題。
再回到剛剛所說的NP和P問題間的關係是否等價？
為了去解決這個問題，科學家們另外提出NPC的概念。假設有天資聰穎Ａ大喊：「我可以在多項式時間內解出NPC了！」，那這時其他科學家，就可以說：
反之，假設有天資聰穎Ｂ大喊：「我可以證明某NPC問題絕對不能在Polynomial Time時間內解決。」這時，科學家們就會說：
有了NPC的概念後，就可以找方法去證明他們之間的關係了～～
主要是從老師上課內容，再自行做成筆記，如有錯誤還請各位不吝指教~~
那今天就先到這裡，我們下次再見～～
