🎯 什麼情境該想到我
當你「卡在一個問題上，怎麼想都只有指數級的解法」的時候。
★ 它的實務價值不是「證明你解不出來」，而是「讓你停止浪費時間找不存在的多項式演算法，轉而去做近似、啟發式、或縮小問題」。
⚙️ 怎麼用（定義與實務判斷）
四個類別（最常被搞混的部分）
| 類別 | 定義 | 白話 |
|---|---|---|
| P | 多項式時間可解 | 能快速算出答案 |
| NP | 多項式時間可驗證 | ★ 給你一個答案，能快速檢查它對不對 |
| NP-hard | 至少和 NP 中最難的問題一樣難（所有 NP 問題都能多項式歸約到它） | 「不比 NP 裡任何問題簡單」 |
| NP-complete | NP-hard 且 自己也在 NP 裡 | 「NP 裡最難的那一批」 |
┌─────────── NP-hard ───────────┐
│ │
┌────┴──── NP ────┐ │
│ ┌─────┐ │ ★ NP-complete │
│ │ P │ │ = NP ∩ NP-hard │
│ └─────┘ │ │
└─────────────────┘ │
│ ↑ │
│ NP-complete │
└───────────────────────────────┘
★ 停機問題：NP-hard 但不在 NP（連驗證都不行）
★ 最常見的誤解：「NP 代表 Non-Polynomial」。不是。
NP = Nondeterministic Polynomial（非確定性多項式時間）。
實務上記住「NP = 答案能被快速驗證」就夠了。
P vs NP：是否 P = NP 仍未解決（千禧年大獎問題）。普遍相信 P ≠ NP，但沒有證明。
★ 怎麼證明一個問題是 NP-complete
① 證明它在 NP 裡 —— 給一個「證書」，說明怎麼在多項式時間驗證
② 找一個已知的 NP-complete 問題 L
③ ★ 證明 L ≤ₚ 你的問題 —— 把 L 的任意實例「多項式時間轉換」成你的問題的實例
（方向別搞反！是把「已知難的」歸約到「你的問題」）
★ 歸約的方向是這題最常見的錯誤。
要證明你的問題很難，就要說明「如果你的問題有快解，那個已知很難的問題也就有快解了」。
反過來（把你的問題歸約到已知難問題）什麼都沒證明——那只說明你的問題不比它難。
Cook-Levin 定理：SAT 是第一個被證明的 NP-complete 問題，之後所有的證明都靠從它（或它的後代）歸約。
值得認得的 NP-complete 問題
認出「我的問題長得像這個」就等於知道不該找精確多項式解：
| 問題 | 長相 |
|---|---|
| SAT / 3-SAT | 布林公式能不能被滿足 |
| ★ 旅行商（TSP） | 走遍所有點的最短迴路 —— 路線規劃、配送 |
| ★ 0-1 背包 | 容量限制下的最大價值 —— 資源分配、預算分配 |
| ★ 圖著色 | 最少幾種顏色使相鄰不同色 —— 暫存器配置、排課、頻譜分配 |
| ★ 裝箱（Bin Packing） | 最少用幾個箱子 —— 虛擬機調度、切割下料 |
| 頂點覆蓋 / 獨立集 / 團 | 圖上的集合問題 |
| 集合覆蓋 | 最少幾個集合能蓋住全部 —— 選監測點、選測試案例 |
| ★ 子集和 / 分割 | 能不能湊出某個和 —— 對帳、分組 |
| ★ 排程（多機、有相依） | —— CI 排程、產線排程 |
★ 加星號的那幾個在真實系統裡到處都是。
「排班」「配送路線」「資源裝箱」「選最少的測試案例」——這些都是 NP-hard，而且你老闆會叫你解。
★ 實務上碰到 NP-hard 該怎麼辦（這才是重點）
不是「放棄」，是「換一種贏法」：
| 策略 | 說明 |
|---|---|
| ① ★ 縮小問題規模 | 時 ，暴力或狀態壓縮 DP 完全可行。 先問「真實的 n 有多大」——常常小到根本不需要擔心 |
| ② ★ 近似演算法 | 接受「不是最佳，但保證不差太多」（見 近似演算法） |
| ③ 啟發式 / 元啟發式 | 貪婪、局部搜尋、模擬退火、遺傳演算法。沒有保證，但實務上常常夠好 |
| ④ ★ 用求解器 | ILP / SAT / CP 求解器（OR-Tools、Gurobi、CP-SAT）。 它們在真實的結構化實例上快得驚人——★ 這是實務上最被低估的選項 |
| ⑤ 參數化 | 某個參數小時可解（fixed-parameter tractable）。例如樹寬小的圖 |
| ⑥ 特例 | 你的實際輸入可能落在可解的子類（如 DAG、二分圖、平面圖） |
| ⑦ ★ 改需求 | 「每天重算一次最佳路線」改成「增量調整昨天的路線」—— 常常是最有效的一招，而且是產品決策不是技術決策 |
★ 面試答法：「我會先確認它真的是 NP-hard（找出對應的經典問題），
然後問真實的 有多大、需要多接近最佳、多久要算完一次。
多數情況下答案是：用 OR-Tools 之類的求解器，或接受一個 95% 品質的貪婪解。」
一個重要的區分
「NP-hard」是關於「最壞情況」與「漸進行為」的陳述。
它不代表「你的那些實例都解不動」。
真實世界的實例通常有結構（稀疏、有階層、有對稱性），求解器可以利用這些結構。
SAT 求解器每天在解上百萬變數的工業實例——理論上的最壞情況和實務上的典型情況是兩回事。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ 歸約方向別搞反（見上）。
- ★ 「NP-hard」不等於「不可解」，更不等於「不可計算」。不可計算的例子是停機問題。
- 不要隨口說「這是 NP 問題」。P ⊂ NP，所以排序也是 NP 問題。你想說的多半是 NP-hard。
- ★ 先確認 的實際大小再擔心。這是最常見的過早優化——很多「NP-hard 的恐慌」在 時完全不成立。
- 啟發式要能量品質。用小規模的暴力解當基準，量出「我的啟發式離最佳有多遠」（見 貪婪演算法 的驗證建議）。
- 最佳化版本 vs 判定版本：嚴格來說 NP-complete 定義在判定問題上（「存在 ≤ k 的解嗎」）；
最佳化版本（「最小的是多少」）通常是 NP-hard。日常對話不區分沒關係，面試最好講對。