1990 - PCP 定理：只讀常數個位元就能驗證#

案件摘要#

1990 年代，PCP（Probabilistically Checkable Proof）定理橫空出世：任何 NP 證明都可以重寫成「只隨機抽查常數個位元、就能以高機率驗證」的形式。Arora–Safra（1992）與 ALMSS（1998）完成證明，並由此證明大量近似問題本質上難解——NP-完備理論的第二次革命。

前因 -- 為什麼會有這個案子#

1979 年 Garey–Johnson 已指出某些問題「連近似都難」，但只是直覺，無嚴格證明。
Papadimitriou 與 Yannakakis（1988/1991）定義 MAX-SNP 類，系統化「近似下界」的探尋，但卡在無法證明任何下界。
1985 年互動式證明革命（IP、Arthur–Merlin）與 1990 年 \(\text{IP} = \text{PSPACE}\) 的算術化技術提供了新武器。
Feige–Goldwasser–Lovász–Safra–Szegedy（1991）率先把互動證明與「可查驗證明」連結，逼近 PCP。
案件動機：證明可以寫得多「耐查」？查幾個位元就夠嗎？

線索與推理 -- 數學式、程式、理論#

PCP 的定義#

機率可查驗證明：一個證明編碼 \(\pi\) （字串）加上驗證者 \(V\) ， \(V\) 使用 \(r(n)\) 個隨機位元、查詢 \(\pi\) 的 \(q(n)\) 個位置：

\[ \text{PCP}(r(n), q(n)) = \{L : \exists V,\ \forall x \in L,\ \Pr[V \text{ 接受}] \ge 2/3\} \]

（其中 \(V\) 只讀 \(\pi\) 的 \(q(n)\) 個位元；對 \(x \notin L\) ，任何偽證都會被抓住，接受率 \(\le 1/2\) 。）

PCP 定理#

\[ \boxed{\text{NP} = \text{PCP}(O(\log n),\ O(1))} \]

等價敘述：存在常數 \(c\) ，使得任何 NP 語言的證明可編碼為 \(\pi\) ，驗證者只需擲 \(O(\log n)\) 個硬幣、只讀 \(c\) 個位元，就能以 \(\ge 2/3\) 機率正確判斷。更強的版本（Raz 1998）：常數可壓到 \(q = O(1)\) 個查詢、完備性 1、健全性任意接近 1。

證明結構（ALMSS 1998，原版約 500 頁分量的五篇論文）#

編碼：把 NP 證明用低次多項式/算術化編碼（繼承 IP = PSPACE 的技術）——錯誤會「擴散」。
組合：把多個低次測試組合成一致性測試（linearity test、low-degree test、BLR 測試）。
歸約：用「可查驗證明」構造出「驗證不到就必有大隙」的約束滿足問題。
平行重複（Raz's parallel repetition theorem）：把健全性誤差指數級壓小。

概念性 Python 模擬（PCP 驗證精神——線性測試 BLR）：

import random

# BLR 線性測試：檢查函數 f 是否線性 f(x XOR y) = f(x) XOR f(y)
def blr_linear_test(f, n, trials=100):
    for _ in range(trials):
        x = random.randint(0, (1 << n) - 1)
        y = random.randint(0, (1 << n) - 1)
        # V 只「查詢」f 在三個點的值 —— 常數個查詢！
        if f(x ^ y) != f(x) ^ f(y):
            return False   # 抓到偽證
    return True            # 通過 → f 以高機率接近線性

# 真線性函數：內積
f_true = lambda x: bin(x).count('1') % 2
print(blr_linear_test(f_true, 8))   # True（幾乎總是通過）

# 偽線性函數：完全隨機 → 被抓機率 = 1/2，100 次後逃脫機率 2^-100
import random as rnd
f_fake = lambda x: rnd.randint(0, 1)
print(blr_linear_test(f_fake, 8, trials=20))  # False（幾乎總是被抓）

PCP 的核心直覺：把證明「代數化」編碼後，任何一處作弊都會讓常數個隨機查詢以常數機率撞見矛盾——錯誤無處可藏。

對近似難度的影響#

PCP 定理把「驗證失敗」轉化為「最佳化解的差距」：驗證者讀到的常數個約束若不可全滿足，就定義了一個 MAX-問題。直接得到：

\[ \text{Max-3SAT: 存在常數 } \epsilon > 0,\ \text{除非 P} = \text{NP，}\ \forall \text{演算法}\ A,\quad \text{ALG}_A < 1 - \epsilon \]

更精確地（Håstad 1997，基於 PCP + 平行重複）：

\[ \text{Max-3SAT 的最佳可能近似比為 } \frac{7}{8} + \epsilon \text{（不可超越，除非 P}=\text{NP）} \]

而隨機賦值就能達到 \(7/8\) ——門檻完全封死：簡單演算法已是最佳。

結案 -- 後果與影響#

近似難度的黃金時代：PCP 定理 + Håstad 技術證明了一長串門檻：Max-Clique 無 \(n^{1-\epsilon}\) 近似、Set-Cover 無 \((1-\epsilon)\ln n\) 近似、頂點覆蓋、著色、排程……Garey–Johnson 書中「難以近似」的直覺終於落地。
理論計算機科學的中心定理：PCP 定理被譽為繼 NP-完備之後最重要的結果，Arora 因此獲 2012 年（與 Barak 等共享的）Gödel 獎與圖靈獎（2021，與 Barak）。
500 頁 → 40 頁：Dinur 2007 以「gap amplification」給出純組合的簡短證明（約 40 頁，僅用歸約與圖擴張），使 PCP 進入研究所課程。
實務餘波：可驗證計算、zk-SNARK（區塊鏈擴容）的技術譜系可直接追溯到 PCP 與低度測試。
定理證明不相對化，是相對化障礙（1975）之後「非黑箱技術」路線的重大勝利。

關鍵人物與文獻#

Sanjeev Arora、Shmuel Safra（1992）："Probabilistic Checking of Proofs: A New Characterization of NP", FOCS 1992 / JACM 1998。
Arora、Lund、Motwani、Sudan、Szegedy（ALMSS, 1998）："Proof Verification and the Hardness of Approximation Problems", FOCS 1992 / JACM 45(3):501–555, 1998。
Johan Håstad（1997/2001）："Some Optimal Inapproximability Results"，Max-3SAT 的 \(7/8\) 門檻。
Ran Raz（1998）："A Parallel Repetition Theorem"。
Irit Dinur（2007）："The PCP Theorem by Gap Amplification", JACM 54(1)——組合證明，40 頁。
Feige、Goldwasser、Lovász、Safra、Szegedy（1991）：PCP 的前身（"Interactive proofs and verifiable proofs"）。