跳轉到

3.2 憑證與驗證器#

概念說明#

上一節我們說「NP 是可以在多項式時間內『驗證』解的問題」，但「驗證」到底驗證什麼？關鍵在兩個工具：憑證（certificate，也稱見證 witness）與驗證器（verifier）。

解一個 NP 問題可能很難，但當有人「宣稱」找到解時，我們可以要求對方附上一份憑證——一組足以證明答案成立的額外資訊。驗證器則是一部（多項式時間的）演算法，它吃進兩樣東西：原始輸入 x 與憑證 c，然後回報「接受」或「拒絕」。

例如： - SAT 問題：憑證是變數的真值賦值。驗證器逐條檢查每個子句是否至少有一個文字為真，時間是線性的。 - 漢米爾頓迴路問題：憑證是頂點的一個排列。驗證器檢查相鄰兩頂點之間是否都有邊，且最後回到起點。 - 整數分解問題：問 n 是否有 1 到 1000 之間的因數。憑證就是那個因數 d，驗證器只需檢查 n % d == 0，這只需一次取模運算。

注意憑證的大小必須受限：我們要求憑證長度是 n 的多項式，且驗證器在「輸入長度 + 憑證長度」的多項式時間內完成。這才是 NP 的精確定義：

一個語言 L 屬於 NP，若且唯若存在多項式 p 與多項式時間機器 V，使得 x ∈ L ⟺ 存在長度不超過 p(|x|) 的字串 c，使 V(x, c) 接受。

這個定義有兩種直觀讀法：解讀一，「存在比所有反證更容易的證明」（驗證容易發現難）；解讀二，NP 是「非決定性圖靈機且多項式時間可解」的問題類，兩者等價。憑證觀點在工程上特別有用——就像數學家的定理證明：找到證明可能要花幾年，但審閱證明只需要一個下午。

一個容易混淆的點是：憑證不一定是「解」本身。例如在「圖是否有大小為 k 的獨立集」問題中，直接給出那 k 個頂點就是最好的憑證；但在某些問題（如互質整數問題）中，憑證可能是更巧妙的輔助資訊（如 Bezout 係數）。設計憑證的訣竅是：找出讓檢查變成純粹機械運算的最低限度資訊。

演算法步驟：撰寫一個驗證器#

  1. 確定問題的決策形式（輸入 x 是什麼、問句是什麼）。
  2. 設計憑證格式：它必須足夠完整，使答案可以機械地被檢查。
  3. 逐項列出驗證條件（例如：每個子句成立／每條邊都存在／權重和不超過上限）。
  4. 實作驗證器 V(x, c)，回傳 True/False。
  5. 分析：驗證時間是否為輸入與憑證大小的多項式？憑證長度是否多項式？若是，此問題屬於 NP。
  6. 反向檢查「完備性」與「健全性」：若答案為是，必須存在某個憑證能通過驗證（完備）；若答案為否，任何憑證都會被拒絕（健全）。

Python 程式碼範例#

# ---------- 通用驗證器 ----------
def verify_SAT(assign, formula):
    """憑證：assign 為 dict {變數: True/False}。
    formula: List[List[int]]，如在組合語言前的通俗寫法，用 +/、*以文字呈現。
    原始形式：每個子句如 [-2, 3, 1] 表示 (¬x2 ∨ x3 ∨ x1)。
    """
    def lit(v):
        return assign[abs(v)] if v > 0 else not assign[-v]
    return all(any(lit(v) for v in clause) for clause in formula)

def verify_clique(graph, k, clique):
    """憑證：clique 是大小為 k 的頂點列表。
    graph 以集合的集合表示鄰接關係。"""
    if len(set(clique)) != k:
        return False
    return all(v in graph[u] for u in clique for v in clique if v != u)

# ---------- 測試 ----------
sat_formula = [[1, 2], [-1, 3], [-2, -3]]   # (x1∨x2) ∧ (¬x1∨x3) ∧ (¬x2∨¬x3)
print(verify_SAT({1: True, 2: False, 3: True}, sat_formula))   # True
print(verify_SAT({1: False, 2: False, 3: False}, sat_formula)) # False
graph = {0: {1, 2}, 1: {0, 2}, 2: {0, 1}}
print(verify_clique(graph, 3, [0, 1, 2]))                     # True

複雜度分析#

  • SAT 驗證器：子句數 m、每子句長度常數（3-SAT）時為 O(m)；一般 CNF 亦為輸入長度的線性。憑證長度為變數數，顯然多項式。
  • 團（Clique）驗證器：k 個頂點兩兩檢查邊存在，用集合查詢為 O(k²)，k ≤ n 故多項式。
  • 共通結論：以上皆屬 NP。驗證的時間單獨看並不代表整個問題的搜尋難度——把憑證的搜尋選項窮舉出來是 2ⁿ 或 m! 級別，這正是 P 與 NP 的分水嶺。

練習#

  1. 請為「整數 n 是否為質數」設計一個簡短的憑證與驗證器。提示：若 n 是合數，提供一個小於 n 的因數即可；若 n 是質數，可以用 Garner 性質給出較小的「質數憑證」（選做）。
  2. 漢米爾頓迴路問題的驗證器：給定鄰接字典 graph 與頂點序列 path，寫出 verify_Hamiltonian(graph, path)，並檢查每個頂點恰出現一次、相鄰頂點有邊、最後一點與第一點相鄰。
  3. 「兩張圖是否同構（Graph Isomorphism）」：憑證是頂點的對應關係。寫出驗證器（時間 O( E )），並討論：找到這個對應可能要窮舉 n! 種情況，這說明了什麼？