3.3 P 是否等於 NP#

概念說明#

先看一個顯而易見的包含關係：P ⊆ NP。任何能被多項式時間演算法直接求解的問題，當然也能在多項式時間內被驗證——只要忽略預設憑證（或取空憑證），驗證器直接重新求解一遍即可。因此 P 是 NP 的子集。

真正的大問題是反方向是否成立：NP ⊆ P 嗎？ 也就是，「所有能快速驗證的問題，是否也都能快速求解？」這就是所謂的 P 對 NP 問題，它是理論資訊科學最具代表性的未解之謎，也是克雷數學研究所懸賞一百萬美元的七大數學難題之一。

為什麼大家傾向相信 P ≠ NP？直觀的理由是：把「尋找」與「檢查」視為對稱能力的看法違反了日常經驗。例如，數獨的解填好後任何人眨眼就能檢查，但一個空盤的數獨可能需要思索很久；一個藥物的分子結構寫出來後很容易模擬驗證其療效，但要「想出」要合成的分子卻非常困難。如果 P = NP，那麼所有這類「創造／尋找」活動都可以靠暴力加多項式加速解決，世界觀會徹底改變。

這不只是純理論問題，它有具體的工程與經濟後果：

密碼學：目前所有現代密碼的安全性都建立在「某類問題（如質因數分解、離散對數）驗證容易、求解困難」之上。若 P = NP 且人們找到高效演算法，目前的公鑰密碼體系可能瓦解。
最佳化：企業每天在解調度、路徑、排程等 NP-hard 問題。如果 P = NP，這些啟發式與近似演算法的產業都可以直接被「精確解演算法」取代。
數學證明：Cook 指出，若 NP 包含的問題都屬 P，則尋找數學定理的證明也將變成多項式時間可解——因為透過類似 Cook-Levin 的編碼，「是否存在長度 ≤ k 的證明」本身就是一個 NP 問題。

從 1971 年 Cook 提出這個問題至今已超過半世紀，人們的認識有兩個重要進展。第一，在 1980 年代，Baker、Gill 與 Solovay 證明了「相對化證明」（relativizing proof，即在圖靈機中加入任意 Oracle 也保持成立的技術）無法解決 P vs NP。第二，在 1990 年代，Razborov 與 Rudich 證明了「自然證明」（natural proofs）的限制，表示用現有的電路面積下界技術也難以直接證明 P ≠ NP。這些結果讓我們明白了「需要更深的技術」，而不是「需要更多努力」。

不過也有少數學者認為 P = NP 也有可能，只是目前的多項式演算法使用了非常巨大的常數，反而無法在實際機器上快速執行。無論走向哪一邊，這個問題背後關於「驗證」與「搜尋」的核心哲學，都值得每個演算法工程師省思。

演算法步驟：用實驗感受「驗證快、搜尋慢」#

選一個屬於 NP 的小問題（本節用 3-SAT）。
分別實作「求解器」（searcher）與「驗證器」（verifier）。
讓求解器採用暴力法（試 2ⁿ 種賦值）。
隨輸入規模 n 增大，記錄求解步數與驗證步數。
觀察兩者的成長曲線差異。

Python 程式碼範例#

import itertools, time

def sat_solver(formula, n):
    """暴力求解 3-SAT：列舉 2^n 種賦值。"""
    steps = 0
    for bits in itertools.product([False, True], repeat=n):
        steps += 1
        assign = {i + 1: bits[i] for i in range(n)}
        ok = all(any(assign[abs(v)] != (v < 0) for v in clause)
                 for clause in formula)
        if ok:
            return assign, steps
    return None, steps

def sat_verifier(assign, formula):
    """驗證一組憑證：m 個子句一次掃描。"""
    return all(any(assign[abs(v)] != (v < 0) for v in clause)
               for clause in formula)

# 實驗
for n in range(3, 15):
    # 有固定的可滿足公式（例）：(x1 ∨ x2 ∨ x3) 只涉及前三變數
    formula = [[1, 2, 3]]
    t0 = time.time()
    sol, st = sat_solver(formula, n)
    dt = time.time() - t0
    verify_steps = len(formula)
    print(f"n={n:2d}  求解遍歷 {st:6d} 種賦值 ({dt:.3f}s)"
          f"  驗證只需 {verify_steps} 步")

複雜度分析#

暴力求解器：2ⁿ 種賦值 × O(m) 驗證 = O(2ⁿ · m)，指數時間。
驗證器：O(m)，多項式（實際上線性）。
觀察上表：n 每增加 1，求解步數加倍；而驗證步數保持不變。這個 2ⁿ 與 1 的極限差距，正是「P ⊊ NP？」猜測想要形式化表達的對象。
理論提醒：如果我們證得「3-SAT 屬於 P」，由於 3-SAT 是 NP-complete（第 4 章會證明），則 P = NP。也就是說，只要為任何一個 NP-complete 問題找到多項式演算法，整個 NP 就塌縮成 P。

練習#

請為「圖是否含有大小為 k 的團（clique）」設計驗證器，並與窮舉 C(n, k) 的求解器搭配，在第 n = 10、k = 4 的小圖上測量兩者的執行次數比。
「若 P = NP，密碼學終將瓦解」這句話中，「終將」需要什麼額外條件？（提示：從理論存在到實際可執行之間，還有常數因子、位元大小、工程實現等問題。）
進階（選做）：閱讀 Razborov「自然證明」概念的通俗介紹，用一至兩段文字說明為什麼「用電路大小下界證明 P ≠ NP」被認為遇到了牆。