本文為交通大學開放式課程上課心得整理。
目前存在著許多演算法無法在多項式時間解決的問題，本章要探討的就是這類型的問題。
Decision and Optimization Problems
通常問題我們可以分成兩類：判定問題（Decision Problems）以及最佳化問題（Optimization Problems），顧名思義分別指必須返回是或否的問題，以及找出最佳答案（通常是最大或最小解）的問題。
以 MST（最小生成樹）問題為例，在最佳化問題中，我們通常會問：如何找到最小生成樹，但在判定問題中，我們則會問：是否存在一個 cost 在 bound 之下的最小生成樹。
在目前無法用多項式時間演算法解開的題目中，我們會用 Decision Problems 的形式去探討，再用 binary search 將解答轉換為 Optimization Problems 的結果。
Complexity Classes
關於演算法時間複雜度的分級，源於1970 年的兩位科學家 Cook 與 Karp，這些等級之間由於分類的定義不同，並不完全互斥，以下介紹幾種分類：
・Class P：問題存在多項式時間的演算法解法，且 p 必須與問題的大小有關
・Class NP：問題可以在多項式時間內驗證
・NP-complete：NP 問題中最困難的，若一個問題被定義為 NP-complete，就代表所有的 NP 問題都能以某種形式轉換成該問題的解法解決；換句話說，如果有一天我們能找出 NP-complete 問題多項式時間的解法，就能將所有的 NP 都變成 Class P
Verification Algorithm and Class NP
前面有提到，NP 問題可以在多項式時間內被驗證，因此就需要一個驗證的演算法。這個演算法會有兩個參數，第一個是需要驗證的 instance 以及 bound，第二個是某個 solution，演算法會驗證 solution 是否符合條件，以及是否小於給定的 bound。
以 TSP 為例，我們會給定 n 個城市（並標出城市之間的距離）以及 bound，讓演算法幫我們驗證是否能在 bound 之內讓 salesman 拜訪每個城市一次，再回到原點。
在這裡我們會驗證這個問題是否屬於 NP，步驟如下：
・隨意做出一個解答
・檢查解答是否符合 TSP 的條件
・檢查路徑的 cost 是否小於等於 bound
上述檢查都可以在 O(n) 時間內完成，所以 TSP 屬於 NP。
The First Proved NPC：Circuit Satisfiability
Circuit Satisfiability 是第一個被證明為 NP-complete 的問題。給定一個組合電路，是否能適當的 assign 0 或 1，使 output 為 1？
Polynomial-Time Reduction
當我們遇到一個新的問題時，不發展新的演算法，而是嘗試使用已知的演算法處理，將問題轉換為相應形式，求得解法之後再轉回去，這就是所謂的多項式時間歸約（Polynomial-Time Reduction）。
多項式時間歸約有兩個要點：
・問題轉換必須在多項式時間內完成
・條件與答案的轉換必須是雙向的
多項式時間歸約的使用時機可以分為三個：
・需要解決一個新問題，但不想從頭發展新演算法時：如果可以用舊的演算法解決新問題，同時也就建立了彼此之間的難度關係
・新問題困難度太高：此時難度會反過來，舊的演算法難度會低於新問題，用以證明新問題無法在多項式時間內解決
・兩個問題一樣難：只要能證明兩者可以互相轉換，即可找到解法
Polynomial Reduction: HC ≤p TSP
接下來使用 Hamiltonian circuit（HC）為例解說多項式時間歸約的使用。HC 問題的描述如下：
給定一個無相圖 G = (V, E)，是否能夠在一筆畫內讓路線經過所有的點，並回到原出發點？目前已知 HC 屬於 NP 問題，這裡將使用 HC 來轉換 TSP，用以證明 TSP 解答的困難度。
首先建構轉換公式，先將 TSP 上所有的城市都轉成 HC 上的點，再將 HC 的圖轉換為 TSP 上的圖。需要特別注意的是，TSP 保證兩點之間一定有邊連結，所以在 HC 中若有兩點之間沒有邊，就必須補上邊，並給定適當距離（通常 HC 已存在的邊預設權重為 1，新增加的邊權重會設定較高，在本例中設定為 2），並將 bound 設定為 n。
接下來要證明當我們可以在 HC 圖中找到一個解法時，TSP 也能找到一個相應的路徑，反之亦然。
・先假設 HC 尚有一條路徑 h 會經過所有的點再回到起始點，此時將該路徑移到 TSP 上也會成立
・由於該路徑會回到原點，故可知其為 HC 原有的 cycle，路徑的權重皆為 1，經過 n 條路徑，cost 總和為 n
・假設從 TSP 的圖中找到一條 cost ≤ n 的路徑，由於是從原點出發又回到原點，所以經過的邊數量為 n，平均分配下來每條邊的權重為 1，故可以得知此 cycle 亦存在於 HC 中
NP-completeness
一個判定問題 L 如果屬於 NP-completeness，那就代表兩件事情（要件，缺一不可）：
・L 屬於 NP Class
・是最難的問題
這裡存在著一個目前尚無解答的問題：P 是否等於 NP？這裡可以分兩個狀況略作探討：
・P = NP：若能找到多項式時間的演算法，此時 L 屬於 P，P 便等於 NP
・P != NP：若能證明 L 無多項式時間解，則 P 不等於 NP
當我們遇到一個問題，想知道他是否屬於 NP-completeness 時，通常會用以下證明方法：
・假設一個判定問題 L 屬於 NP-completeness，則：
- L 屬於 NP Class
- 找到另一個已知的 NP 難題 L ’，並讓 L ’ 的問題能在多項式時間內轉換到 L 上
從上面的範例可知，HC 與 TSP 符合上述證明敘述，故 TSP 也是 NP-completeness。
Linear Programming
線性規劃（Linear Programming）與動態規劃一樣，都是一個最佳化的過程，不過在這裡它強調裡面所使用的式子都是線性。動態規劃可以從兩個地方觀察：
・會有一個最佳化的目標
・會有條件限制，這些限制會規範出問題解答的空間（flexible vision）
動態規劃包含三大部分：
・在制定演算法之前，必須先規劃用來做決策的變數
・要有一個目標函數，能得到最大／最小的解
・針對問題本質提出限制
在最佳化的過程中，有幾個有趣的現象，以下一一探討。
Multipliers
由於線性規劃是求最大／最小值，自然會希望知道 Upper Bound，因此要嘗試利用變數的資訊來找到 Upper Bound：
multiplier 指的就是在求取 Upper Bound 時所使用的乘數，以上方範例來看，第一個組合的 multiplier 為（1, 6, 0），第二個組合為（0, 5, 1），最佳化的過程事實上就是求取 multiplier 的過程。
Duality
如上所述，求取原始問題的 Upper Bound 可以轉換成求取 multiplier：
此時可以看見兩個問題之間的對偶性（求取最大的獲利，等同於找出最小的 multiplier）。
如果一個線性規劃的問題有最佳解，其對偶問題也能找到最佳解，同時兩個解答會收斂在一起。
The Simplex Algorithm
線性規劃的條件限制會圍出解答的空間，會是平面、立體或是更高維度的空間端看給定條件而定。由於圍出的範圍會是一個多邊形，因此求取極端值的方式就是對邊角做驗證，沿著最佳解答的方向前進，直到周圍再也找不到比自己更好的解為止。
由於頂點是由平面（或線）的交集所形成的，彼此之間只會有一個條件不同，因此要從一個頂點移動到相鄰的下一個頂點（或找到下一個頂點做比較），只要換掉其中一個面（二維平面的話就是另一個構成點的條件）即可。
Simplex Algorithm 會以原點（所有的變數都是 0）為出發點，依序和相鄰的點比較，在每個執行步驟會做兩件事：
・當下的解答是否是最好的
・如果是，則停在原地，如果不是，則移動到最好的頂點去
Simplex Algorithm 為了讓動作單純化，還有一個座標轉換的機制，使得每次的頂點都在原點上，如此只要確認（被轉換過的）原點係數是否為負，就會知道目前的位置是否是最佳解。
若是一開始的設定就沒有任何點在原點上，那就先做座標轉換，讓某個點成為原點再開始執行演算法即可。
Standard Form
由於每個人設計出來的 Linear Programming 樣子很不整齊，因此在使用上有一個描述的格式，稱為標準式（Standard Form）。標準式的幾個原則如下：
・採用最小化方向（minimize cost function）
・所有的限制都是等式
・所有的變數皆不為負
在線性規劃中，限制通常以不等式的狀態出現居多，為了讓它符合標準式，這邊引入一個叫做 slack variable 的概念，將每個限制中小於的量以變數（必不為負）的概念引入，讓原本的限制變成等式（以上述例子來看，x1 ≤ 200 可以轉換成 x1 加上某個值之後會變成 200，若要讓 x = 200，只要再引入一個大於等於零的變數進入函示中即可，下面以此類推）。
針對標準式求到的解，也可以在原始函式中找到對應解。
Linear Programming 在問題過大或變數過多時執行效率不佳，使用時需特別注意。
