[Algorithm] NP-完備理論

理論概念

動態規劃把很多看似會爆炸的問題壓回多項式時間，但有些問題連 DP 也救不回來——0/1 knapsack 看似 $O(nW)$ 很漂亮，但 $W$ 是數值，真正的輸入長度是 $\log W$ ，嚴格來說它只是 pseudo-polynomial。NP-完備理論就是替這類「目前找不到真正多項式演算法」的問題，建立一套統一的難度分類：把所有「能快速驗證答案」的判斷問題放進 NP；在 NP 裡最難的那一層叫 NP-complete；證明一個問題是 NPC，等於承認「除非 $\text{P} = \text{NP}$ ，否則不可能快又精確」，合法地轉向近似、heuristics、特例。

核心分類

多項式 vs 指數

一個演算法的執行時間若能被某個 $n$ 的多項式 $p(n) = O(n^k)$ 蓋住（ $k$ 是常數），就稱作多項式時間（polynomial time）。

類型	範例複雜度	直覺
多項式	$O(1)$ 、 $O(\log n)$ 、 $O(n)$ 、 $O(n \log n)$ 、 $O(n^2)$ 、 $O(n^3)$	輸入加倍、時間乘常數倍
指數	$O(2^n)$ 、 $O(n!)$	輸入多 1 個，時間可能翻倍

為什麼要以多項式劃界？工程上可接受的界線：輸入放大 10 倍， $O(n^3)$ 只慢 1000 倍， $O(2^n)$ 直接爆到天上去。

簡單問題（tractable）：已知有多項式時間演算法能解
困難問題（intractable）：目前沒有已知的多項式演算法

「困難」不是「證明沒有」，而是「人類還沒找到」——這個措辭差別正是 P vs NP 至今未解的原因。

最佳化版 vs 判斷版

同一個問題通常有兩種問法：

最佳化（optimization）：找出最好的解，例「最短路徑長度是多少？」
判斷（decision）：yes / no，例「是否存在長度 $\le k$ 的路徑？」

NP 理論圍繞判斷問題設計。理由：

判斷問題只有兩個輸出（yes / no），好用圖靈機與邏輯精確定義
最佳化一律可包裝成判斷：最佳化版有多項式解 $\iff$ 對應判斷也有多項式解
因此「判斷版是困難的 $\implies$ 最佳化版至少一樣難」

後面所有 NP-completeness 的討論都以 decision 版為主。

P、NP、NP-hard、NPC

類別	定義	直覺
P	有多項式時間演算法能解出的判斷問題	我能自己找到答案
NP	有多項式時間演算法能驗證答案的判斷問題	別人遞答案給我，我能快速檢查
NP-hard	NP 裡的任何問題都能多項式轉換到它（至少跟 NP 一樣難）	可能不在 NP 裡（例：halting problem）
NP-complete（NPC）	同時是 NP 且 NP-hard	NP 裡最難的那一層

NP 不是「non-polynomial」的縮寫，是「Nondeterministic Polynomial」——在能「同時試所有分支」的非決定性圖靈機上多項式時間可解。更好懂的等價定義是驗證版：

$L \in \text{NP}$ $\iff$ 存在多項式時間驗證器 $V$ ，使得對任何 $x \in L$ ，都有長度多項式的「證書」 $c$ 讓 $V(x, c) = \text{yes}$ 。

以 SAT 為例：證書就是變數賦值，驗證就是代進公式算一遍， $O(|F|)$ 線性。TSP decision 的證書是一條 cycle，驗證是加總長度 $O(n)$ 。

顯然 $\text{P} \subseteq \text{NP}$ （能解就能驗證）。 $\text{P} = \text{NP}$ ？ 電腦科學千禧年問題之一，目前主流相信 $\text{P} \neq \text{NP}$ ，但沒人證出來。

15 個經典 NP-complete 問題

下表先彙整 15 個經典困難問題，全部都是 NP-complete。解開任何一個，等於全部解開——因為它們彼此多項式時間可互相轉換。

#	問題	輸入	輸出（decision 版）
1	SAT	一條布林公式	有沒有賦值讓公式為真？
2	3-SAT	CNF，每個 clause 3 個 literal	同上
3	0/1 Knapsack	物品 + 容量 + 價值門檻	選得出價值 $\ge V$ 且重量 $\le W$ 的組合嗎？
4	TSP	有權完全圖	有長度 $\le k$ 的 Hamiltonian cycle 嗎？
5	Vertex Cover	無向圖	有 $\le k$ 個頂點 cover 所有邊嗎？
6	Graph Coloring	無向圖 + $k$	能用 $k$ 色染相鄰不同色嗎？
7	Set Cover	集合族	有 $\le k$ 個子集 cover 全 universe 嗎？
8	Exact Cover	集合族	存在「互不重疊且聯集 = U」的子集選法嗎？
9	Subset Sum	整數組 + 目標 $t$	有子集和剛好 $t$ 嗎？
10	Partition	整數組	能切成兩半讓兩半和相等嗎？
11	Bin Packing	物品大小 + 箱容量	用 $\le k$ 個箱裝得下嗎？
12	Max Clique	無向圖	有 $\ge k$ 個頂點的完全子圖嗎？
13	Hamiltonian Cycle	無向圖	有經過每頂點恰一次的 cycle 嗎？
14	Art Gallery	多邊形	用 $\le k$ 個守衛能看到所有內部點嗎？
15	VLSI Layout	矩形集合	能塞進面積 $\le A$ 的 bounding box 嗎？

15 題個別說明

1. SAT（Satisfiability）

給布林公式 $F$ （由變數 $x_1, x_2, \ldots$ 和運算子 $\land, \lor, \neg$ 組成），問是否存在賦值讓 $F$ 為 true。以 $n$ 個變數來看，暴力窮舉要 $2^n$ 組。SAT 是所有 NPC 問題的祖師爺——Cook-Levin 定理（1971）先證了它，其他問題再透過轉換間接得證。

2. 3-SAT

SAT 的受限版：公式必須是 CNF（conjunctive normal form），若干 clause 用 $\land$ 串起來，每個 clause 剛好 3 個 literal 用 $\lor$ 串起來。3-SAT 仍然是 NPC，且語法固定，實務上常當「reduction 起點」去 reduce 到別的問題。

3. 0/1 Knapsack（decision 版）

給 $n$ 個物品（重 $w_i$ 、值 $v_i$ ）、容量 $W$ 、價值門檻 $V$ ，問是否存在子集總重 $\le W$ 且總值 $\ge V$ 。DP 的 $O(nW)$ 看似多項式，但 $W$ 編碼長度是 $\log W$ ，實際是 $O(n \cdot 2^{\log W})$ ——指數於輸入長度。這種「對數值多項式、對長度指數」叫 pseudo-polynomial。

4. 旅行推銷員（TSP）

$n$ 個城市兩兩有距離，找每城市恰訪一次再回起點的 cycle，總距離最小。decision 版：存在長度 $\le k$ 的這種 cycle 嗎？暴力 $(n-1)!/2$ ；DP（Held-Karp） $O(n^2 \cdot 2^n)$ ——比暴力好，但仍指數。幾乎是 NPC 的代表吉祥物。

5. 頂點涵蓋（Vertex Cover）

給 $G=(V, E)$ ，找最小頂點子集 $S$ 使每條邊至少一端在 $S$ 裡。有趣互補： $S$ 是 vertex cover $\iff V \setminus S$ 是 independent set，所以 vertex cover 和 max independent set 是同一個問題兩種包裝。

6. 著色問題（Graph Coloring）

給 $G$ 和色數 $k$ ，能否把頂點染成 $k$ 色使相鄰頂點不同色？ $k=2$ 是多項式（判二部圖，DFS 即可）； $k \ge 3$ 是 NPC。4 色定理雖然說平面圖一定能 4 色，但最小色數一般仍難算。

7. 集合涵蓋（Set Cover）

給 universe $U$ 和子集族 $\mathcal{S}$ ，找最少個子集使聯集等於 $U$ 。貪婪那篇提過——每次選「蓋到最多新元素」，達 $O(\ln n)$ 近似比，精確解 NP-hard。

8. 精準涵蓋（Exact Cover）

要求選出的子集彼此不重疊，聯集仍等於 $U$ ——每個元素恰被一個選中子集覆蓋。數獨、鋪磚都可轉成 exact cover，所以 Knuth 的 Dancing Links (DLX) 很紅。

9. 子集合之和（Subset Sum）

給整數組 $A$ 和目標 $t$ ，問存在子集和剛好等於 $t$ 。knapsack 去掉價值欄位的簡化版，仍 NPC（pseudo-polynomial）。

10. 切割（Partition）

給整數組，能否切成兩組 $A_1, A_2$ 使 $\sum A_1 = \sum A_2$ 。subset sum 的特例（ $t = \frac{1}{2}\sum A$ ），一樣 NPC。

11. 裝箱（Bin Packing）

$n$ 個物品每個大小 $\le C$ ，每 bin 容量 $C$ ，最少用幾 bin 裝完？貪婪那篇的 FFD 是 $\frac{11}{9}$ -approximation，實務上夠用。

12. 最大完全子圖（Max Clique）

找最大的「兩兩互相有邊」頂點子集。和 independent set 完全對偶： $G$ 中的 clique 就是補圖 $\bar G$ 的 IS，所以 Clique、IS、VC 三兄弟互為轉換。

13. 漢米爾頓迴圈（Hamiltonian Cycle）

圖中是否存在經過每頂點恰一次再回起點的 cycle。和 Euler cycle（每條邊恰走一次）差別要分清：Euler 可 $O(E)$ 判（連通且所有頂點度數為偶），Hamiltonian 就卡死了。

14. 藝廊問題（Art Gallery）

多邊形展場，最少幾個「守衛」放裡面讓每個點都被至少一個守衛看到？Chvátal 定理： $n$ 邊簡單多邊形最多需 $\lfloor n/3 \rfloor$ 個，但最小守衛數仍 NP-hard。

15. VLSI 布局

把矩形模組塞進最小 bounding box（同時滿足線路、引腳約束）。現代晶片設計核心問題，實務靠 heuristics、SA、遺傳演算法。

Reduction 與 NPC 證明

Reduction 的定義與方向

定義：問題 $A$ 多項式時間可轉換到 $B$ （記作 $A \le_p B$ ）：若存在多項式時間函式 $f$ ，把 $A$ 的每個輸入 $x$ 變成 $B$ 的輸入 $f(x)$ ，使得

x \in A \iff f(x) \in B.

直覺：若我能解 $B$ ，就能解 $A$ ——先把輸入 $x$ 透過 $f$ 轉成 $B$ 的輸入，再用 $B$ 的解法，整體還是多項式時間。換句話說：

A \le_p B \implies B \text{ 至少跟 } A \text{ 一樣難.}

方向很容易搞反： $A \le_p B$ 是「 $A$ 較易、 $B$ 較難」，不是反過來。

一個簡單例：Independent Set $\le_p$ Vertex Cover。

觀察： $S$ 是 $G$ 的 IS $\iff V \setminus S$ 是 VC
轉換：「 $G$ 有大小 $\ge k$ 的 IS 嗎？」 $\leftrightarrow$ 「 $G$ 有大小 $\le n-k$ 的 VC 嗎？」
函式 $f(G, k) = (G, n-k)$ ， $O(1)$ 完成

只要 VC 有多項式解，IS 也就有。

證 NPC 的標準兩步

$L$ 是 NP-complete 若：(1) $L \in \text{NP}$ ；(2) 所有 $L' \in \text{NP}$ 都有 $L' \le_p L$ 。第二條叫 NP-hard，NPC = NP ∩ NP-hard。

關鍵推論：若任一 NPC 問題有多項式演算法，則 $\text{P} = \text{NP}$ 。等價地：若相信 $\text{P} \neq \text{NP}$ ，NPC 問題永遠沒有多項式精確解。

證一個問題 $L$ 是 NPC 的標準流程：

Step 1: 證 L ∈ NP           ← 給多項式驗證器
Step 2: 取已知 NPC 問題 A
Step 3: 建 f : A → L 的多項式轉換
Step 4: 證 x ∈ A  ⟺  f(x) ∈ L

第一步通常簡單（證書 + 驗證很直接），第二步是核心。NPC 就這樣從 SAT 一個接一個建出來：

\text{SAT} \le_p \text{3-SAT} \le_p \text{VC} \le_p \text{Clique} \le_p \text{Hamiltonian} \le_p \text{TSP} \le_p \ldots

新問題要證 NPC 不用回頭爬到 SAT，找個「顯然可 reduce 過來」的已知 NPC 起點就行。

經典 reduction 範例

Cook-Levin：SAT 是 NPC（根節點）

1971 年 Cook（後由 Levin 獨立提出類似結果）從頭證了 SAT 是 NP-complete——直接從「任何 NP 問題都可以模擬成一條 CNF」這個最底層起手，不靠別人 reduce。

這是 NP-completeness 整棵樹的根。細節涉及把非確定性圖靈機的計算歷程編碼成布林變數與 clause：每個時間步、每個帶格狀態、每個轉移規則都轉成 clause，最後合取起來得到一條 CNF，其可滿足性等價於原機器在多項式步內接受輸入。

證明不好讀，初學看個大方向就好——重點在於底層的第一個 NPC 是由機器模型直接證的，後面都是 reduction chain。

SAT

\le_p

3-SAT：把任意 clause 拆成 3-literal

關鍵想法：任何 SAT clause 都可以改寫成等價的一組「每條 clause 剛好 3 個 literal」的 clause 集合。

規則：

1 個 literal $x$ ：補兩個新變數 $y, z$ ，擴成 4 條：

$(x \lor y \lor z) \land (x \lor y \lor \neg z) \land (x \lor \neg y \lor z) \land (x \lor \neg y \lor \neg z)$

$y, z$ 所有組合都寫下來後 AND 起來，等價於「 $x$ 必須為 true」。
2 個 literal $(x_1 \lor x_2)$ ：補一個新變數 $y$ ，擴成 2 條：

$(x_1 \lor x_2 \lor y) \land (x_1 \lor x_2 \lor \neg y)$
3 個 literal：不動。
$k > 3$ 個 literal $(l_1 \lor l_2 \lor \cdots \lor l_k)$ ：引入 $k - 3$ 個新變數 $y_1, \ldots, y_{k-3}$ 「串」起來：

$(l_1 \lor l_2 \lor y_1) \land (\neg y_1 \lor l_3 \lor y_2) \land \cdots \land (\neg y_{k-3} \lor l_{k-1} \lor l_k)$

具體例： $(x_1 \lor x_2 \lor x_3 \lor x_4)$ （ $k = 4$ ）引入 1 個新變數 $y_1$ ，變成：

$(x_1 \lor x_2 \lor y_1) \land (\neg y_1 \lor x_3 \lor x_4)$

驗證：若原 clause 至少一個 literal 為 true，必能選一個 $y_1$ 值讓兩條 3-clause 都滿足；反之若原 clause 全 false，這兩條無論 $y_1$ 怎麼選都有一條會是 false——等價。

每條原 clause 只膨脹成常數條或 $O(k)$ 條新 3-clause，線性時間完成——reduction 成立。

3-SAT

\le_p

Clique：公式變成圖

要證：有個辦法把 3-SAT instance 變成一個圖，使得公式可滿足 $\iff$ 圖有大小 $\ge m$ 的 clique（ $m$ 是公式的 clause 數）。

建圖：對公式裡每個 clause 的每個 literal 各造一個頂點（共 $3m$ 個）。連邊規則：兩頂點 $u, v$ 之間有邊 iff

$u, v$ 屬於不同 clause
$u, v$ 對應的 literal 不互補（不是 $x$ 和 $\neg x$ ）

論證：

公式可滿足 $\implies$ 有 $m$ -clique：取每個 clause 中已被賦值為 true 的那個 literal（每 clause 至少有一個）。這 $m$ 個頂點兩兩屬於不同 clause、也絕不互補（都是 true，不可能一個 $x$ 一個 $\neg x$ ），兩兩有邊——就是大小 $m$ 的 clique。
有 $m$ -clique $\implies$ 公式可滿足：同 clause 內部沒邊，clique 每個 clause 最多取一個；加起來 $m$ 個就剛好每 clause 一個。又因非互補，可同時賦值為 true——公式可滿足。

整個轉換多項式時間、等價性成立——reduction 完成。

Clique

\le_p

\le_p

VC：三兄弟互轉

Clique $\le_p$ IS：輸入 $(G, k)$ 轉成 $(\bar G, k)$ （補圖）。clique 和 IS 對偶。
IS $\le_p$ VC： $(G, k) \to (G, n-k)$ ，前面示範過。

一路 chain 下去就把 15 個問題全證成 NPC。

常見考法

#	題型	重點
1	P / NP / NPC / NP-hard 定義辨析	P 能解；NP 能驗證；NPC = NP ∩ NP-hard；NP-hard 不必在 NP 裡（可能更難）
2	給問題判斷屬於哪一類	排序、MST、最短路徑 → P；SAT、TSP、Knapsack → NPC；Halting → 比 NPC 還難
3	寫多項式驗證器證 $L \in \text{NP}$	給定答案（證書）→ 多項式時間檢查；如 SAT 代入賦值、TSP 加 cycle 長度
4	Reduction $A \le_p B$ 的方向性	$A$ 比 $B$ 容易；解 $B$ 就能解 $A$ ； $B$ 至少跟 $A$ 一樣難
5	SAT → 3-SAT 擴展規則	$k$ literal 要 $k-3$ 個新變數串起來
6	3-SAT → Clique 建圖規則	每 literal 一頂點；不同 clause 且不互補才連邊； $m$ -clique ↔ 可滿足
7	IS / VC / Clique 三兄弟互轉	IS 補圖 → Clique；VC = $V \setminus$ IS
8	Pseudo-polynomial 的意思	$O(nW)$ 對數值多項式，但 $W$ 編碼長度是 $\log W$ ，對輸入長度指數
9	2-SAT vs 3-SAT 差異	2-SAT 是 P（implication graph + SCC）；3-SAT 才是 NPC
10	Hamiltonian vs Euler 差異	Euler（邊）： $O(E)$ 可判；Hamiltonian（點）：NPC

考試常踩的陷阱

NP 不是「non-polynomial」：是「Nondeterministic Polynomial」；NP ⊇ P
NP-hard 不一定在 NP 裡：例如 halting problem 是 NP-hard 但不是 NPC（連驗證都做不到）
Reduction 方向搞反： $A \le_p B$ 表示「 $A$ 較易、 $B$ 較難」，不是反過來
只證 $L \in \text{NP-hard}$ 不夠：還要證 $L \in \text{NP}$ 才能成為 NPC
0/1 Knapsack 的 DP $O(nW)$ 不算多項式解： $W$ 以二進位編碼是 pseudo-polynomial
2-coloring 是 P、3-coloring 是 NPC：門檻就在 2 vs 3

知道一個問題是 NP-complete 並不代表該放棄，只是承認「不可能快又精確」。實務上有三條退路：縮小輸入範圍、容忍近似解、容忍機率。下一篇會進入這些技巧——回溯法與分支設限精確搜（小規模下可行）、近似演算法（犧牲精度換多項式）、以及它們各自的適用情境。

Latest Updates

2026.04.15 Content updated