10.1 如何判斷一個新問題是否NP-hard#

概念說明#

遇到一個新問題時，判斷其複雜度是設計演算法前的第一步。流程有兩個方向：證明它「容易」（在 P 中），或證明它「至少和某個已知難題一樣難」（NP-hard）。實戰判斷可以拆成標準步驟：

第一步：找相似問題。 把新問題的描述與已知 NP-complete 家族比對——約束滿足（3-SAT）、數值分割（SUBSET-SUM）、圖結構選取（頂點覆蓋、集團、獨立集）、路徑巡訪（漢米爾頓、TSP）、覆蓋與包裝（集合覆蓋）。絕大多數 NP-hard 問題都能對號入座。

第二步：限制條件實驗。 嘗試把問題的特殊情況改到最簡單：若一個問題的「極度特例」已知是 NP-hard（例如「k = 3 的圖著色」），那原問題必然 NP-hard，這叫限制化約（restriction），是所有化約技巧中最省力的——不需要任何構造，只需指出「你的問題允許某種特例，而該特例是 NP-complete 的」。

第三步：構造化約。 若沒有現成特例，選一個結構最接近的源頭問題，設計多項式時間轉換（如第六章的三個範例）。記住三要件：轉換多項式時間、yes 實例對應 yes、no 對應 no。

第四步：找演算法的機會。 若問題有特殊結構（樹狀輸入、參數小、數值範圍小、區間結構），可能存在 DP、FPT 或特殊多項式演算法。證明 NP-hard 只排除「一般情形的多項式」，從不排除「你的實例」被有效率解決。

最後提醒兩個常見錯誤：（1）「我找不到多項式演算法」不構成證明；（2）問題是優化版本時，證明其判定版本 NP-complete、再說明優化解可給出判定答案，即可得 NP-hard。

演算法步驟#

寫下問題的形式化定義（輸入、輸出、目標）。
檢查輸入的特殊結構（是否為樹、DAG、區間圖、平面圖？參數是否自然地小？）。
嘗試已知的多項式套路：貪婪、DP、二分答案、網路流、匈牙利演算法。
均失敗後，比對 NP-complete 家族找「長得最像」的源頭問題。
先試限制化約：能否把源頭問題變成新問題的特例？
不行則設計 gadget 化約，並用小實例以程式驗證解的對應。
寫下完整的化約證明（轉換 + 正確性雙向論證 + 複雜度分析）。

Python 程式碼範例#

（以「排程問題是否 NP-hard」為例，展示限制化約的驗證思路）

from itertools import combinations

# 新問題：給 n 個工作（時長）與 m 台相同機器，
# 問能否在期限 T 內完工？（多機排程 P||Cmax）
# 限制化約：m = 2 時，問題 = 「能否分成兩組、
# 各組總和 ≤ T」。令 T = sum/2 即 PARTITION！
# => 多機排程是 NP-hard。

def two_machine_schedule(jobs, T):
    """m=2 排程判定 = SUBSET-SUM 變體"""
    total = sum(jobs)
    if T * 2 < total:
        return False
    half = min(T, total)
    dp = {0}
    for j in jobs:
        dp |= {s + j for s in dp if s + j <= T}
    return any(total - s <= T for s in dp)

def brute_schedule(jobs, T):
    for r in range(len(jobs) + 1):
        for S in combinations(jobs, r):
            if sum(S) <= T and sum(jobs) - sum(S) <= T:
                return True
    return False

jobs, T = [3, 5, 7, 9], 12
print(two_machine_schedule(jobs, T),
      brute_schedule(jobs, T))   # 一致：True True

複雜度分析#

限制化約：零構造成本，是證明 NP-hard 的首選武器；本章例子中 m = 2 的多機排程即為分割問題。
判定版到優化版的推論：若判定版 NP-complete 且優化解能在多項式時間內被檢查，則優化版 NP-hard。
化約驗證的計算成本：用程式在隨機小實例上交叉驗證「化約後的答案 = 原問題答案」，能在寫證明前抓住大多數構造錯誤。
正向機會檢查：樹上 DP、k 小參數、小值域這三條線索值得在任何「宣告 NP-hard」之前先排除。

練習#

證明「背包優化版」是 NP-hard：給定判定版是 NP-complete 的前提，寫出從優化解到判定答案的轉換。
多機排程在 m 固定為 3 時仍是 NP-hard（由分割化約），但若所有工作時長都相等呢？設計多項式演算法。
選一個你熟悉的現實問題（如大學考試排程、快遞路線），完成第 1~5 步的判斷流程，寫出你的結論與理由。