跳轉到

4.1 化約的觀念#

概念說明#

想一想這個情境：你遇到一個新問題 A，花了好幾個月都想不出高效演算法。此時你偶爾發現，問題 B（你早知道它很難）可以「轉化成」問題 A——只要你能替 A 找到高效演算法，把 B 的解也順手拿到。這說明：A 至少跟 B 一樣難。這就是化約的核心思想。

在 NP 理論中，最常用的化約形式是 Karp 化約（也稱多項式時間多對一化約）。我們說「問題 A 化約到問題 B」（記作 A ≤ₚ B），指的是存在一個多項式時間的函數 f，能把 A 的每個實例 x 映射到 B 的實例 f(x)，並且：

x 是 A 的「是」實例 ⟺ f(x) 是 B 的「是」實例。

注意兩個關鍵點：

  1. 方向性。符號 ≤ₚ 讀作「不大於」，因此「A ≤ₚ B」表示 A 的難度不超過 B。新手最容易犯的錯就是把方向弄反：如果你想證明「我的新問題 A 很難」，你應該把已知的難問題 B 化約到 A，而不是把 A 化約到 B。記憶口訣：「難的東西流到哪裡，那裡就跟著難」。
  2. 化約本身必須是多項式時間。若化約是超多項式的（例如需要 2ⁿ 步轉換），它就失去意義——因為就算 B 有快速演算法，你套上慢的化約函數之後，整體流程也不會快。

化約具有傳遞性：若 A ≤ₚ B 且 B ≤ₚ C，則 A ≤ₚ C。這個性質使「NP-complete」這個概念得以成立：SAT ≤ₚ 3-SAT、3-SAT ≤ₚ 子集合加總、子集合加總 ≤ₚ 背包……一連串難問題形成一條化約鏈，只要鏈的源頭是 NP-complete，整條鏈上的問題都是 NP-hard。

還有一個容易忽視的細節：化約是問題之間的，而不是解之間的。正確的句式是：「給定 B 的一個解 f(x)，我能推導出 A 的一個解 x」——這需要構造「Turing 化約」（帶 Oracle 的呼叫式化約），見練習 1。

演算法步驟：構造一個化約證明#

  1. 選定已知難的來源問題 B（最好是 NP-complete）。
  2. 設計轉換函數 f：把 B 的實例参数轉化為 A 的實例。
  3. 證明 f 的正確性：x 是 B 的「是」實例 ⟺ f(x) 是 A 的「是」實例（通常是兩個方向的「當且僅當」）。
  4. 分析 f 的複雜度：必須是多項式（最好是線性或二次）。
  5. 當 A 也是 NP 時，即可宣告 A 為 NP-complete。

Python 程式碼範例：從獨立集化約到頂點覆蓋#

一個「大小為 k 的獨立集」（Independent Set）化約為「大小為 n−k 的頂點覆蓋」（Vertex Cover）的關鍵觀察是：在一個圖 G 上，「找出 k 個互不相鄰的頂點」與其補集「找出 n−k 個能覆蓋舞台上每條邊的頂點」是同一件事的兩面——一個頂點集合 S 是獨立集，若且唯若 V∖S 是頂點覆蓋。

def reduce_IS_to_VC(n, edges, k):
    """輸入：G 有 n 個頂點、edge 集合 edges、目標大小 k。
    輸出：等價的 Vertex Cover 實例 (n, edges, n - k)，
    使得「G 有大小 k 的獨立集」 ⟺ 「G 有大小 n-k 的覆蓋」。
    """
    return (n, edges, n - k)

def is_independent(n, edges, S):
    return all(u not in S or v not in S for (u, v) in edges)

def is_vertex_cover(n, edges, T):
    return all(u in T or v in T for (u, v) in edges)

# 驗證化約的正確性（暴力對照）
import itertools
n_test, edges_test, k_test = 4, [(0,1), (1,2), (2,3)], 2
n2, e2, k2 = reduce_IS_to_VC(n_test, edges_test, k_test)
for S in itertools.combinations(range(n_test), k_test):
    T = set(range(n_test)) - set(S)
    # 精確對應：S 是獨立集 ⟺ V-S 是覆蓋
    same = is_independent(n_test, edges_test, set(S)) == is_vertex_cover(n2, e2, T)
    print(set(S), T, "一致" if same else "不一致！")

運行結果應該全部顯示「一致」，這說明化約在所有結構上是正確的。這也示范了化約證明可以用程式驗證——你在數學證明時寫下的「若且唯若」，在程式上就是一次逐字對照。

複雜度分析#

  • 化約函數 f 只是「複製 n 與 edges、把 k 換成 n−k」，時間 O(1)，極小化約。
  • 化約函數的代價 c·nᵈ 與目標問題的解法 time_B 相加：若 time_B 是多項式 nᵇ，則 time_A ≤ c·nᵈ + c'·(n+c·nᵈ)ᵇ 仍是多項式。
  • 反之，若 time_A 是超多項式，也不能把 B 拖下水——這是化約的單向性。

練習#

  1. 我們說化約是「問題之間」的關係，因此需要一定是多項式時間。請說明為什麼例中使用的 Turing 化約（把 A 的實例帶進 B 的解，再轉換回來）嚴格地說只能得到「隸屬於 Pᴮ」這個結論，而不直接是「A ≤ₚ B」。（提示：Turing 化約允許呼叫 B 的解多次。）
  2. 「圖是否為二部圖（Bipartite）」化約到「圖是否能用 2 色著色」。請寫出這個顯然成立的化約函數 Python 實作。
  3. 頂點覆蓋問「是否存在大小 ≤ k 的覆蓋」；獨立集問「是否存在大小 ≥ n−k 的獨立集」。請仔細比對這裡的 ≤ 與 ≥ 號，說明化約中「忘了反轉方向」會導致什麼樣的錯誤證明。