3.1 驗證與搜尋：NP的定義#

概念說明#

想像你的朋友宣稱「我找到一張九宮格數獨的解了」。要相信他，你不需要重新從頭解數獨——只要逐格檢查他填的數字是否滿足各行各列各宮的不重複規則即可，幾秒鐘就能完成。這個現象點出了 NP 的核心思想：

NP 是「解正確性可以被多項式時間驗證」的問題集合。

技術上 NP 代表「非決定性多項式時間」（Nondeterministic Polynomial time），這個名字暗示了它的原始定義（非決定性圖靈機猜測再驗證），但對學習者最友善的理解是驗證的角度。

必須澄清幾個常見誤解：

NP 不代表 "Not Polynomial"。「非多項式」的問題類是別的東西；NP 的 N 指的是 nondeterministic。
NP 的問題不一定難。事實上 P ⊆ NP：能在多項式時間「解出」的問題，當然也能多項式時間「驗證」（自己重解一遍即可）。
真正的問題是：P 是否也涵蓋了全部 NP？即 P =? NP。尚未有人能證明或反證。

許多真實問題都具備「驗證很快」的性質：數獨、叉積方程式是否存在解答、工作排程是否能滿足所有期限、圖是否有 k 色著色、背包是否能不超重地裝滿價值。它們的共同點是：搜尋空間龐大（指數或階乘級），但每個候選解的檢查只需多項式時間。

驗證 V.S. 搜尋的對偶#

每個 NP 問題其實包含兩個層面：

驗證問題（decision + certificate）：給定實例 x 與憑證 c，判斷 c 是否讓 x 成為「是」實例。若能在 poly(|x|) 時間完成，問題就屬於 NP。
搜尋問題：不要憑證，自己把 c 找出來。這才是實務上的困難所在。

搜尋版本可以在多項式時間化約為驗證版本（用逐步定案與自涵化約技巧，本書不深究細節），所以「解到」比「驗證到」在一個多項式因子內不會更難到指數級，但仍然可能難上一個多項式因子——而 NP 完全性理論顯示許多問題的搜尋版本與其最佳演算法已達數十年研究卻仍在指數時間。

演算法步驟：判斷一個問題是否像是 NP#

定義問題為決策形式：答案是否為「是／否」？（如「是否存在長度 ≤ k 的路徑」而不是「求最短」）
定義憑證的格式：什麼樣的 c 可以宣稱答案是「是」？（如一組變數賦值、一個子集合、一個頂點順序）
寫出驗證器：檢查 c 是否合法且滿足問題條件。
分析驗證器時間：若與 |x|（＋可能大小受限的 c）呈多項式關係，該問題屬於 NP。
記得憑證必須大小受多項式限制——若 c 得用天文數字的資訊才能表達，就不算。

Python 程式碼範例#

用數獨（把 n=9 推廣到任意框寬）示範「驗證快、搜尋慢」。

def verify_sudoku(matrix):
    """驗證 9x9 數獨解：驗證時間 O(n^2)，與搜尋時間的指數級形成對比"""
    n = len(matrix)
    k = int(n ** 0.5)
    rows = set()
    for r in range(n):
        rows.add(tuple(matrix[r]))
    for c in range(n):
        if sorted(col := [matrix[r][c] for r in range(n)]) != list(range(1, n + 1)):
            return False
    for br in range(k):
        for bc in range(k):
            block = [matrix[br*k + i][bc*k + j]
                     for i in range(k) for j in range(k)]
            if sorted(block) != list(range(1, n + 1)):
                return False
    return all(sorted(set(row)) == list(range(1, n + 1))
               for row in matrix) and len(rows) == n and matrix[0][0] == matrix[0][0]

def valid_solution(board):
    """完整、簡潔的驗證器"""
    n = len(board); k = int(n ** 0.5)
    want = set(range(1, n + 1))
    ok_units = (
        all(set(row) == want for row in board) and
        all({board[r][c] for r in range(n)} == want for c in range(n)) and
        all({board[br*k + i][bc*k + j] for i in range(k) for j in range(k)} == want
            for br in range(k) for bc in range(k))
    )
    return ok_units

solved = [[5,3,4,6,7,8,9,1,2],
          [6,7,2,1,9,5,3,4,8],
          [1,9,8,3,4,2,5,6,7],
          [8,5,9,7,6,1,4,2,3],
          [4,2,6,8,5,3,7,9,1],
          [7,1,3,9,2,4,8,5,6],
          [9,6,1,5,3,7,2,8,4],
          [2,8,7,4,1,9,6,3,5],
          [3,4,5,2,8,6,1,7,9]]
print("驗證數獨解:", valid_solution(solved))   # True，瞬間完成

bad = [row[:] for row in solved]; bad[0][0] = 6
print("驗證錯誤解:", valid_solution(bad))      # False，同樣瞬間

驗證只對每列、每欄、每宮各做一次集合比較，時間 O(n²)——對 n = 9 的數獨而言不到一毫秒。然而求解（搜尋）版本的數獨是一般化的廣義數獨，已被證明是 NP-complete，一般求解器需仰賴回溯與剪枝，困難實例（如著名的 17 個提示數的最小數獨）可能需要探索大量節點。

複雜度分析#

驗證數獨：三重檢查（列 n、欄 n、宮 √n×√n 個），每次集合比較 O(n)，總 O(n²)，空間 O(n)。
搜尋數獨：最壞情況需考慮每個空格可填 n 種數字，搜尋樹達指數級 O(n^m)（m 為空格數）。這正是 NP 問題的「不對稱之美」——驗證多項式、搜尋可能指數。
一般地，屬於 NP 的條件是「存在多項式時間的驗證器 V 且憑證長度為多項式」。驗證器本身會用到的時間通常寫作 poly(|x|)，其中 |x| 是實例的輸入長度。

練習#

定義「子集合加總」問題：給定數字集合 S 與目標 t，是否存在子集合總和恰為 t？請寫出其驗證器（給定憑證子集合），並分析驗證時間與憑證長度。
「判定一個質數」屬於哪一類？請說明為什麼 primality 測試在 AKS 演算法出現前就已被認為「大概很快」（提示：驗證用的憑證很少）。
有人宣稱：「搜尋問題都屬於 NP」。請指出這個敘述的錯誤之處：搜尋問題通常不是決策問題，NP 的定義只針對「是／否」語言；搜尋版本要用什麼方式關聯到 NP？（提示：思考「是否存在解」的決策形式。）