第三部分：計算複雜度¶

< 上一題：平攤分析 | 返回目錄 | 下一題：NP 證明 >

場景：查詢優化的困境¶

SearchX 的查詢優化器需要選擇最佳的索引組合。有 \(n\) 個可能的索引，選哪些能讓查詢最快？

你跑了一週的演算法，結果還在算。主管問：「這演算法是不是寫壞了？」

「不是我寫壞了，是這問題本身就很難...但怎麼證明？」

第 6 題：為什麼有些問題很難 - NP 基礎¶

計算複雜度理論幫助我們理解問題的**本質難度**。

(a) P 與 NP 的定義¶

4 分 ・大三

你需要知道：P 和 NP 類別的精確定義

題目：

定義 P 類別
定義 NP 類別
解釋為什麼 P ⊆ NP

解答

1. P 類別：

可以在**多項式時間**內**解決**的決策問題

形式化：存在演算法 \(A\) 和多項式 \(p(n)\)，對任何輸入 \(x\)： - \(A\) 在 \(O(p(|x|))\) 時間內輸出正確答案

例子：排序、最短路徑、最大流

2. NP 類別：

可以在**多項式時間**內**驗證**答案的決策問題

形式化：存在驗證器 \(V\) 和多項式 \(p(n)\)，對任何 YES-instance \(x\)： - 存在「證據」\(c\)（certificate），\(|c| \le p(|x|)\) - \(V(x, c)\) 在 \(O(p(|x|))\) 時間內輸出 YES

例子：SAT、Hamiltonian Path、Subset Sum

3. 為什麼 P ⊆ NP？

如果問題在 P 中，我們可以在多項式時間**解決**它。

驗證？直接忽略證據，重新計算答案！

所以任何 P 問題自動在 NP 中。

┌────────────────────────────┐
│           NP               │
│   ┌──────────────────┐    │
│   │        P         │    │
│   │  (可解 = 可驗證)  │    │
│   └──────────────────┘    │
│     (只能驗證，未知能否快速解) │
└────────────────────────────┘

(b) NP-Complete 的定義¶

4 分 ・大三（考古題 110 Q12）

你需要知道：NP-Complete 為什麼是「最難的 NP 問題」？

題目：

定義 NP-Hard
定義 NP-Complete
如果 P ≠ NP，NP-Complete 問題有多項式時間解嗎？

解答

1. NP-Hard：

「至少和 NP 中任何問題一樣難」

形式化：問題 \(H\) 是 NP-Hard 若： - 對於**所有** \(L \in\) NP，\(L \le_p H\)

（\(\le_p\) 表示多項式時間歸約，見下一小節）

注意：NP-Hard 不一定在 NP 中！

2. NP-Complete：

NP-Hard + 在 NP 中

\[\text{NP-Complete} = \text{NP-Hard} \cap \text{NP}\]

3. 如果 P ≠ NP：

假設某個 NP-Complete 問題 \(C\) 有多項式時間解。

則對任何 \(L \in\) NP： - \(L \le_p C\)（因為 \(C\) 是 NP-Hard） - 用 \(C\) 的多項式解來解 \(L\)

這意味著所有 NP 問題都在 P 中，即 P = NP，矛盾！

結論：若 P ≠ NP，則 NP-Complete 問題**沒有**多項式時間解。

┌───────────────────────────────────┐
│            NP-Hard                │
│  ┌───────────────────────────┐   │
│  │           NP              │   │
│  │  ┌─────────────────────┐ │   │
│  │  │   NP-Complete      │ │   │
│  │  │   (NP ∩ NP-Hard)   │ │   │
│  │  └─────────────────────┘ │   │
│  │  ┌───────────┐           │   │
│  │  │     P     │           │   │
│  │  └───────────┘           │   │
│  └───────────────────────────┘   │
└───────────────────────────────────┘

© 多項式時間歸約¶

4 分 ・大三

你需要知道：如何用歸約比較問題的難度？

題目：

定義多項式時間歸約（Polynomial-time Reduction）\(A \le_p B\)
如果 \(A \le_p B\) 且 \(B \in P\)，則 \(A \in P\)。為什麼？
如果 \(A \le_p B\) 且 \(A\) 是 NP-Hard，則 \(B\) 是 NP-Hard。為什麼？

解答

1. 多項式時間歸約：

\(A \le_p B\)（A 可歸約到 B）若存在多項式時間函數 \(f\) 使得：

\[x \in A \Leftrightarrow f(x) \in B\]

直觀：「如果我能解 B，就能解 A」

A 的實例 x ──f──► B 的實例 f(x) ──解 B──► 答案
     │                                    │
     └──────────── 答案相同 ───────────────┘

2. 如果 B ∈ P，則 A ∈ P：

解 A 的演算法： 1. 把 \(x\) 轉換成 \(f(x)\)：\(O(p(n))\) 時間 2. 用 B 的多項式演算法解 \(f(x)\)：\(O(q(p(n)))\) 時間 3. 返回答案

總時間：多項式，所以 \(A \in P\)。

3. 如果 A 是 NP-Hard，則 B 是 NP-Hard：

對任何 \(L \in\) NP： - \(L \le_p A\)（因為 A 是 NP-Hard） - \(A \le_p B\)（給定） - 所以 \(L \le_p B\)（歸約的傳遞性）

因此 B 是 NP-Hard。

歸約的方向很重要！

已知	歸約方向	結論
B ∈ P	A ≤ₚ B	A ∈ P
A 是 NP-Hard	A ≤ₚ B	B 是 NP-Hard

(d) 經典 NP-Complete 問題¶

3 分 ・大三

你需要知道：常見的 NP-Complete 問題

題目：

列出 5 個經典的 NP-Complete 問題，並簡述每個問題。

解答

經典 NP-Complete 問題：

問題	描述
SAT	給定布林公式，存在使其為真的賦值嗎？
3-SAT	SAT 但每個子句最多 3 個變數
Vertex Cover	用最少 \(k\) 個點覆蓋所有邊？
Clique	存在大小為 \(k\) 的完全子圖？
Independent Set	存在大小為 \(k\) 的獨立集？
Hamiltonian Path	存在經過每個點恰一次的路徑？
Subset Sum	存在子集使和恰好為 \(S\)？
Set Cover	用最少 \(k\) 個集合覆蓋全集？
3-Coloring	能用 3 種顏色著色使相鄰不同色？

歸約關係圖：

                SAT
                 │
                 ▼
               3-SAT
               /    \
              ▼      ▼
       3-Coloring  Vertex Cover
                      │
                      ▼
               Independent Set
                      │
                      ▼
                   Clique

(e) NP 類別的推理¶

4 分 ・大三（考古題 114 Q17）

你需要知道：如何推理 NP 類別之間的關係？

題目：

判斷以下敘述的真假，並說明理由：

如果 A ∈ NP 且 A ∈ NP-Hard，則 A 是 NP-Complete
如果 A 是 NP-Complete 且 A ≤ₚ B，則 B 是 NP-Complete
如果 A 是 NP-Complete 且 B ≤ₚ A，則 B 是 NP-Complete
如果 P = NP，則所有 NP 問題都是 NP-Complete

解答

1. 真

這就是 NP-Complete 的定義：NP ∩ NP-Hard

2. 假（但 B 是 NP-Hard）

A 是 NP-Hard，A ≤ₚ B，所以 B 是 NP-Hard ✓
但 B 不一定在 NP 中！

反例：B 可能是不可判定問題（如 Halting Problem）

3. 假

B ≤ₚ A 只說明 B「不比 A 難」
B 可能在 P 中！

例如：Sorting ≤ₚ SAT（排序後檢查是否有解），但 Sorting ∈ P

4. 真

如果 P = NP： - 對於任何非平凡的 L ∈ NP： - L 在 NP 中 ✓ - L 是 NP-Hard：因為任何 NP 問題都在 P 中，都可以多項式歸約到 L

注意：「非平凡」指的是不是空集合或全集合

(f) 決策問題 vs 最佳化問題¶

3 分 ・大二

你需要知道：NP 理論只處理決策問題

題目：

區分決策問題和最佳化問題
為什麼 NP 定義只用決策問題？
如何把最佳化問題轉成決策問題？

解答

1. 區分：

類型	輸出	例子
決策問題	YES/NO	「存在權重 ≤ k 的路徑嗎？」
最佳化問題	最佳值	「最短路徑的權重是多少？」

2. 為什麼只用決策問題？

決策問題輸出只有兩種，便於定義「驗證」
決策問題的複雜度類別更乾淨
最佳化版本**至少**和決策版本一樣難

3. 轉換方法：

最佳化問題：「找最小的 TSP 路徑」

決策版本：「存在長度 ≤ k 的 TSP 路徑嗎？」

如果能解決策版本，可以用二分搜尋找最佳值
所以最佳化 ≥ 決策（難度）

第 6 題小結：你的複雜度類別地圖¶

「這問題為什麼這麼難？」
    │
    ├─► (a) P vs NP
    │       → P: 能快速解
    │       → NP: 能快速驗證
    │
    ├─► (b) NP-Complete
    │       → NP 中「最難的」問題
    │
    ├─► (c) 多項式歸約
    │       → 比較問題難度的工具
    │
    ├─► (d) 經典問題
    │       → SAT, Vertex Cover, Clique...
    │
    ├─► (e) 推理練習
    │       → 歸約方向很重要！
    │
    └─► (f) 決策 vs 最佳化
            → NP 只處理決策問題

複雜度類別全景圖：

┌─────────────────────────────────────────────────┐
│                   所有問題                       │
│  ┌──────────────────────────────────────────┐  │
│  │              可判定問題                    │  │
│  │  ┌────────────────────────────────────┐ │  │
│  │  │            NP-Hard                 │ │  │
│  │  │  ┌──────────────────────────────┐ │ │  │
│  │  │  │           NP                  │ │ │  │
│  │  │  │  ┌────────────────────────┐  │ │ │  │
│  │  │  │  │    NP-Complete         │  │ │ │  │
│  │  │  │  │   (若 P ≠ NP)          │  │ │ │  │
│  │  │  │  └────────────────────────┘  │ │ │  │
│  │  │  │  ┌───────────┐               │ │ │  │
│  │  │  │  │     P     │               │ │ │  │
│  │  │  │  └───────────┘               │ │ │  │
│  │  │  └──────────────────────────────┘ │ │  │
│  │  └────────────────────────────────────┘ │  │
│  └──────────────────────────────────────────┘  │
└─────────────────────────────────────────────────┘

< 上一題：平攤分析 | 返回目錄 | 下一題：NP 證明 >