4.2 NP-hard 與 NP-complete 的定義#

概念說明#

有了化約工具，我們終於可以精確地定義所謂「最難的問題」。這些定義看似簡單，卻蘊含了整個 NP 理論的骨架。

NP-hard（NP 困難）：問題 B 是 NP-hard，若每一個 NP 中的問題 A 都滿足 A ≤ₚ B。直觀地說，B 至少和整個 NP 一樣難——所有 NP 問題都能「透過 B」間接解決。注意 NP-hard 不要求 B 本身屬於 NP。例如圖靈機的停機問題（Halting Problem）既不在 NP（它不可判定，更別說多項式驗證），卻是 NP-hard；近年的最佳化問題（如最佳化的 TSP，而非決策版 TSP）也常是 NP-hard 而非嚴格意義下的 NP-complete。

NP-complete（NP 完備）：問題 B 同時滿足兩個條件： 1. B ∈ NP（它本身有提出憑證的能力）；以及 2. B 是 NP-hard。

NP-complete 問題是「NP 中最難的那一層」。它們之間有非常密切的關聯：

若任何一個 NP-complete 問題被發現有多項式時間演算法，則所有 NP 問題都有，即 P = NP。反之，若有一個 NP-complete 問題被證明沒有多項式時間演算法，則 P ≠ NP。

因此，「 solving 一個」與「 solving 全部」等價。這就是為什麼 NP-complete 問題清單成為演算法工程師的必修功課：3-SAT、子集合加總（SUBSET SUM）、分割（PARTITION）、0-1 背包（KNAPSACK）、團（CLIQUE）、獨立集（INDEPENDENT SET）、頂點覆蓋（VERTEX COVER）、3-著色（3-COLORING）、漢米爾頓迴路（HAMILTONIAN CYCLE）、旅行銷售員（TSP，決策版）等。

一個常見的問答：「既然 NP-complete 問題可以在 NP 中驗證，清楚它們的難度，那 P 類問題中是否也有『NP-complete』？」答案是沒有（除非 P = NP）。證明：任何 P 中的問題 A，對任何 NP-hard 的 B 滿足 A ≤ₚ B，但這並不使 A 成為 NP-complete——NP-complete 要求「NP 中所有問題都能化約到 A」，這需要 A 是 NP-hard。若某 P 問題 A 同時是 NP-hard，那麼所有 NP 問題都可透過 A 解出成多項式時間，所以 P = NP。因此在 P ≠ NP 假設下，NP-complete 問題全部嚴格位於 NP 之外。

另外一個實務會用到的概念是NP-hard 決策問題 vs. 最佳化問題。例如「是否存在長度 ≤ K 的 TSP 路徑」是決策問題（是/否答案，可在 NP 中驗證），是 NP-complete；而「求出最短 TSP 路徑」是最佳化問題，不改變其一一對應的難度本質，但邏輯上它不在 NP，只能稱為 NP-hard。工程人在討論時，務必區分這兩者。

概念腳本：用程式「模擬」NP-hard 的意義#

# 概念程式：展示「若 子集合加總 有多項式演算法 → 3SAT 也能」的思想鏈
# 我們不會真的開「多項式演算法」（那還未有人寫出），
# 但我們用 Python 模擬「透過一個已寫好 (示意) 的
# 多項式 solvable SUBSET SUM oracle，破 3SAT」的概念。
from itertools import product

def subset_sum_oracle(nums, target):
    """示範用的子集合加總『假想多項式』求解器（實際是暴力）。"""
    for r in range(len(nums) + 1):
        for combo in product(range(len(nums)), repeat=r):
            pass  # 這裡可簡化，重點在「假設」有更快的演算法
    return None

# 這裡指出「化約鏈」的關鍵思想：
# 3SAT --(化約)--> 子集合加總 --(假想多項式)--> 多項式判 3SAT
#                                                ↓
#    oulder 3SAT 是 NP-complete，表示所有 NP 問題也可解 → P=NP
print("3SAT ≤ₚ SUBSET SUM ≤ₚ KNAPSACK ≤ₚ ... ")

真正的 NP-hard「攻擊鏈」在第 6 章會用真實可執行的程式碼展示：給定一條 3SAT 公式，程式自動把它轉換成 SUBSET SUM 實例，再用 SUBSET SUM 求解器反推出 3SAT 的賦值。

複雜度分析與意義#

NP-complete 清單上的每一個問題，目前最好的已知演算法都是指數級（或近乎指數級）。
假設 P ≠ NP，以下三個陳述等價：某些問題屬於 NP 但不屬於 P；3-SAT 屬於 P；任何 NP-complete 問題屬於 P。
NP-hard+NP 屬於 NP-complete；獨立集與頂點覆蓋透過縮小 k 值可在參數化意義下「部分解決」（見第 9 章）。

練習#

請證明：若 SAT 是 NP-complete，且 SAT ≤ₚ 3-SAT，則 3-SAT 也是 NP-complete。（包含兩部分：3-SAT ∈ NP，以及 3-SAT 是 NP-hard。）
為什麼「停機問題」（Halting Problem）是 NP-hard 但不屬於 NP？（提示：它甚至不是可判定的；但對任何 NP 問題，可以用它來此前提下「問有沒有 has 十七在一個 ⟹ 機器在 T 步內答『是』」。）
想一想：如果你負責開發排課系統，遇到一個新問題，你會如何用「查表 + 化約證明」快速確認它是 NP-complete？請描述流程。