第三部分：計算複雜度¶

< 上一題：NP 基礎 | 返回目錄 | 下一題：近似演算法 >

場景：廣告投放最佳化¶

SearchX 有 \(n\) 個廣告位，每個位置可以放多種廣告。目標：選出一組廣告，使總收益最大且不超過預算。

產品經理問：「最佳解是什麼？」你回答：「這是 NP-Complete。」

「你說 NP-Complete，怎麼證明？」

第 7 題：NP-Complete 證明技巧¶

證明一個問題是 NP-Complete 需要兩步：在 NP 中 + NP-Hard。

(a) NP-Complete 證明框架¶

3 分 ・大三

你需要知道：NP-Complete 證明的標準步驟

題目：

說明證明問題 \(X\) 是 NP-Complete 的兩個步驟。

解答

Step 1：證明 X ∈ NP

給定實例 \(x\) 和「證據」\(c\)： - 說明證據是什麼 - 證明驗證可以在多項式時間完成

Step 2：證明 X 是 NP-Hard

從已知 NP-Complete 問題 \(Y\) 歸約： - 設計轉換函數 \(f\)：\(Y\) 的實例 → \(X\) 的實例 - 證明 \(f\) 是多項式時間 - 證明 \(y \in Y \Leftrightarrow f(y) \in X\)

證明 X 是 NP-Complete
        │
        ├─► Step 1: X ∈ NP
        │       → 定義證據
        │       → 驗證是多項式時間
        │
        └─► Step 2: Y ≤ₚ X（Y 是已知 NPC）
                → 設計轉換 f
                → f 是多項式時間
                → 證明等價性

(b) 3-SAT → Vertex Cover¶

5 分 ・大三（考古題 109 Q15b）

你需要知道：經典的 NP-Complete 歸約

題目：

用 3-SAT 歸約到 Vertex Cover，證明 Vertex Cover 是 NP-Complete。

提示

為每個變數建立「選擇」結構，為每個子句建立「滿足」結構

解答

Step 1：Vertex Cover ∈ NP

證據：一組頂點 \(S\)
驗證：檢查 \(|S| \le k\) 且每條邊至少一端在 \(S\) 中
時間：\(O(|V| + |E|)\) = 多項式 ✓

Step 2：3-SAT ≤ₚ Vertex Cover

給定 3-SAT 實例，有 \(n\) 個變數 \(x_1, \ldots, x_n\) 和 \(m\) 個子句 \(C_1, \ldots, C_m\)。

構造圖 \(G\)：

(1) 變數組件：對每個變數 \(x_i\)

x_i ────── ¬x_i

創建一條邊連接 \(x_i\) 和 \(\neg x_i\)。

(2) 子句組件：對每個子句 \(C_j = (a \vee b \vee c)\)

    a_j
   /   \
  /     \
b_j ─── c_j

創建三角形，三個頂點對應子句中的三個文字。

(3) 連接：從每個子句頂點連到對應的變數頂點

例如：\(C_1 = (x_1 \vee \neg x_2 \vee x_3)\)

子句三角形的 a_1 連到 變數組件的 x_1
子句三角形的 b_1 連到 變數組件的 ¬x_2
子句三角形的 c_1 連到 變數組件的 x_3

設定 k：\(k = n + 2m\)

正確性證明：

(→) 若 3-SAT 有解： - 從每個變數組件選「真」的那個：\(n\) 個頂點 - 從每個子句三角形選「假」的兩個：\(2m\) 個頂點 - 總共 \(k = n + 2m\) 個頂點 - 所有邊都被覆蓋 ✓

(←) 若有 \(k\) 個頂點的 Vertex Cover： - 變數組件必須選 \(\ge 1\) 個，三角形必須選 \(\ge 2\) 個 - 總共至少 \(n + 2m\)，所以每組件恰好選最少 - 三角形有一個頂點沒選，它必須被變數組件覆蓋 - 這說明對應的文字為真，子句滿足 ✓

© Vertex Cover → Independent Set¶

3 分 ・大三

你需要知道：利用問題間的互補關係

題目：

證明 Independent Set 是 NP-Complete。

解答

觀察：\(S\) 是 Vertex Cover ⟺ \(V \setminus S\) 是 Independent Set

證明： - \(S\) 覆蓋所有邊 ⟺ 每條邊至少一端在 \(S\) - ⟺ 沒有邊的兩端都在 \(V \setminus S\) - ⟺ \(V \setminus S\) 是 Independent Set

歸約：

Vertex Cover 實例：\((G, k)\) Independent Set 實例：\((G, |V| - k)\)

\(G\) 有 \(k\)-Vertex Cover ⟺ \(G\) 有 \((|V|-k)\)-Independent Set

轉換時間：\(O(1)\)
Independent Set ∈ NP：證據是獨立集，驗證沒有邊即可

(d) Independent Set → Clique¶

3 分 ・大三

你需要知道：補圖的應用

題目：

證明 Clique 是 NP-Complete。

解答

觀察：\(S\) 是 \(G\) 的 Independent Set ⟺ \(S\) 是 \(\bar{G}\) 的 Clique

其中 \(\bar{G}\) 是 \(G\) 的補圖： - 相同的頂點集 - \((u,v) \in E(\bar{G}) \Leftrightarrow (u,v) \notin E(G)\)

歸約：

Independent Set 實例：\((G, k)\) Clique 實例：\((\bar{G}, k)\)

轉換時間：\(O(|V|^2)\) 建補圖
Clique ∈ NP：證據是頂點集，驗證兩兩有邊即可

(e) Subset Sum¶

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

你需要知道：數值問題的 NP-Complete 證明

題目：

Subset Sum：給定 \(n\) 個正整數 \(a_1, \ldots, a_n\) 和目標值 \(S\)，是否存在子集使和恰為 \(S\)？

證明 Subset Sum 是 NP-Complete（從 3-SAT 歸約）。

解答

Step 1：Subset Sum ∈ NP

證據：選中的元素集合
驗證：加總檢查等於 \(S\)
時間：\(O(n)\) ✓

Step 2：3-SAT ≤ₚ Subset Sum

設 3-SAT 有 \(n\) 個變數和 \(m\) 個子句。

構造數字（以 \(10\) 為基底，\(n+m\) 位數）：

對每個變數 \(x_i\)： - 數字 \(v_i\)：第 \(i\) 位是 1，加上對應出現在子句中的位 - 數字 \(v'_i\)：\(\neg x_i\) 的對應數字

對每個子句 \(C_j\)： - 輔助數字 \(s_j, s'_j\)：第 \((n+j)\) 位分別是 1 和 2

目標值 \(S\)： - 變數位（前 \(n\) 位）：每位是 1 - 子句位（後 \(m\) 位）：每位是 3

例子：\(\phi = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3)\)

	\(x_1\)	\(x_2\)	\(x_3\)	\(C_1\)	\(C_2\)
\(v_1\)	1	0	0	1	0
\(v'_1\)	1	0	0	0	1
\(v_2\)	0	1	0	1	0
\(v'_2\)	0	1	0	0	0
\(v_3\)	0	0	1	0	1
\(v'_3\)	0	0	1	1	0
\(s_1\)	0	0	0	1	0
\(s'_1\)	0	0	0	2	0
\(s_2\)	0	0	0	0	1
\(s'_2\)	0	0	0	0	2
S	1	1	1	3	3

正確性：

變數位 = 1：每個變數恰好選一個（\(v_i\) 或 \(v'_i\)）
子句位 = 3：子句至少被一個文字滿足 + 輔助數字補齊

(f) 歸約證明技巧總結¶

3 分 ・大三

你需要知道：如何選擇歸約來源？

題目：

總結 NP-Complete 歸約的常見策略。

解答

歸約來源選擇：

目標問題類型	常用來源
圖問題	3-SAT, Vertex Cover
數值問題	3-SAT, Subset Sum
排程問題	3-SAT, Partition
集合問題	3-SAT, Set Cover

設計轉換的技巧：

變數 → 選擇結構
每個變數對應一個「二選一」的結構
子句 → 約束結構
確保至少一個文字為真
數字編碼
用不同位數代表不同約束
選足夠大的基底避免進位

證明等價性的檢查：

原問題有解
    ⟹ 構造出的實例有解（正向）
    ⟸ 從解讀回原問題的解（反向）

第 7 題小結：你的 NP 證明工具箱¶

「怎麼證明 NP-Complete？」
    │
    ├─► (a) 證明框架
    │       → Step 1: 在 NP 中
    │       → Step 2: NP-Hard（歸約）
    │
    ├─► (b) 3-SAT → Vertex Cover
    │       → 變數組件 + 子句三角形
    │
    ├─► (c) Vertex Cover → Independent Set
    │       → 補集關係
    │
    ├─► (d) Independent Set → Clique
    │       → 補圖
    │
    ├─► (e) 3-SAT → Subset Sum
    │       → 數字編碼技巧
    │
    └─► (f) 策略總結
            → 選對來源，設計結構

經典歸約路線圖：

                         SAT
                          │
                          ▼
                       3-SAT
                      /   |   \
                     ▼    ▼    ▼
            3-Coloring  Vertex   Subset
                        Cover     Sum
                          │        │
                          ▼        ▼
                    Independent  Partition
                        Set
                          │
                          ▼
                       Clique

證明清單：

問題	在 NP 中	歸約來源
3-SAT	賦值驗證	SAT
Vertex Cover	頂點集驗證	3-SAT
Independent Set	獨立集驗證	Vertex Cover
Clique	完全子圖驗證	Independent Set
Subset Sum	加總驗證	3-SAT
Hamiltonian Path	路徑驗證	3-SAT

< 上一題：NP 基礎 | 返回目錄 | 下一題：近似演算法 >