P, NP, NP-Complete：為什麼有些題目無解

一個千禧大獎的問題

P = NP？ 這是計算機科學最大的未解問題之一，證明它對或錯能拿一百萬美金（克雷數學研究所獎金）。

放心，你不需要證明它。但你需要知道這個分類，因為它告訴你：

• 哪些問題確定有效率解
• 哪些問題目前無解、未來可能也沒解
• 遇到後者怎麼辦

P：有效率能解的

P (Polynomial)：能在多項式時間內解出的問題。

具體：時間複雜度是 O(n^k) for some constant k——例如 O(n), O(n²), O(n³), O(n log n)。

例子：

• 排序：O(n log n)
• 最短路徑：O((V+E) log V)
• 雜湊查詢：O(1)
• 線性方程組：O(n³)

這些都「算得完」——n 變大時時間漲得還能接受。

NP：能快速驗證的

NP (Nondeterministic Polynomial)：給你一個候選答案，能在多項式時間驗證對不對。

關鍵字：驗證，不是找。

例子：子集合加總問題

• 問題：給一堆數字，能不能挑幾個加起來等於 100？
• 找答案可能要試 2ⁿ 種組合（很慢）
• 但給你一組答案「{17, 23, 60}」，你 O(n) 就能驗證它對

P ⊆ NP：能解的當然也能驗證（直接用解算法跑一遍 = 驗證）。

NP-Hard / NP-Complete：最難的那群

• NP-Hard：「至少跟 NP 中最難的題目一樣難」
• NP-Complete (NP-C)：NP-Hard 而且自己在 NP 裡

NP-C 是 NP 的「天花板」——如果你能在多項式時間解 NP-C 中的任一題，所有 NP 問題都能解（會證明 P = NP）。

經典 NP-Complete 問題

這些問題到目前為止沒人能找到多項式時間解：

問題	描述
SAT	給一個布林公式，能不能讓它為真？
3-SAT	SAT 的特殊版（每個 clause 3 個 literal）
Knapsack 決策版	n 個物品有重量和價值，能不能裝出總價值 ≥ V 且重量 ≤ W？
TSP	旅行推銷員：經過 n 個城市各一次回到起點，最短路徑？
Vertex Cover	圖中選最少節點，覆蓋所有邊
Graph Coloring	用 k 種顏色幫圖塗色，相鄰節點不同色
Hamiltonian Cycle	圖中能不能找一個經過每個節點一次的環？
Subset Sum	子集合加總到目標值
Clique	圖中找大小 k 的完全子圖

視覺化

怎麼證明一個問題是 NP-Complete？

Reduction（歸約）：把已知的 NP-Complete 問題 A 轉換成你的問題 B。

如果 A 能在多項式時間轉成 B 的特例，B 至少跟 A 一樣難。

第一個被證明是 NP-Complete 的問題是 SAT（Cook-Levin Theorem, 1971）。之後所有 NP-C 都是從 SAT 一路歸約來的：

SAT → 3-SAT → Vertex Cover → Clique
                            → Subset Sum → Knapsack
       → Hamiltonian → TSP
       → Graph Coloring

這章記住

1. P = 能解，NP = 能驗證。P ⊆ NP。
2. NP-Complete = NP 中最難的那群——目前沒人能在多項式時間解。
3. 經典 NP-C：SAT, TSP, Knapsack, Subset Sum, Vertex Cover, Graph Coloring——背幾個。
4. 遇到 NP-C：近似 / 啟發式 / 特殊情況——別硬解。
5. P vs NP 是千禧大獎問題，至今未解。