PCP 定理（PCP theorem）
/ P-C-P /
想像有人遞給你一份一千頁、證明某個困難主張的證明，而你必須判斷它是否正確——但你只被允許讀其中隨機的三個字。你想必會漏掉錯誤。PCP 定理（機率可檢驗證明）做出驚人的斷言：這本質上是可能的——任何有證明的主張，都能改寫成一種特殊的強健格式，使驗證者擲幾枚硬幣、只讀「常數」個位元就能檢查，並以高機率抓出任何有瑕疵的證明。
說得更仔細，它是一個關於 NP 類的定理——那些 YES 答案有簡短、多項式時間可檢驗證書的問題。PCP 定理說 NP = PCP(O(log n), O(1))：每個 NP 問題都有一套證明系統，其中驗證者只用 O(log n) 個隨機位元、只讀證明中 O(1)（常數個）位元，卻能做到（完備性）真陳述的正確證明永遠被接受，且（健全性）假陳述的任何「證明」都以至少（比如說）1/2 的機率被拒絕。神奇之處在於：普通證明是脆弱的——改一個符號，正確性就可能恰好繫於那一點——而 PCP 格式的證明被編碼成讓「任何」錯誤都污染證明的一個常數比例，使得抽查幾個隨機位置就能偵測到。把一份普通證明轉成這種「錯誤被攤開」的形式，正是定理深邃的技術核心。
為何一個關於證明檢查的定理屬於近似這一章：它是不可近似性的引擎。這個關聯（「PCP 對間隙」的對應）在於：一個讀常數個位元的機率驗證者，能被編碼成一個約束滿足實例，而完備性對健全性的間隙（永遠接受 對 半數時候拒絕）就變成 YES 與 NO 實例的最佳值之間一道無法跨越的間隙。那道被製造出的間隙，正是製造間隙的歸約所需要的，所以 PCP 定理正是解鎖銳利的近似困難性結果的關鍵——對 MAX-3SAT、集合覆蓋、團等等許多問題。關於範圍的誠實：這個定理是一個深刻且出了名繁複的結果（它的證明是複雜度理論中最難的之一）；它在 P != NP 下刻畫最壞情況的難度，並解釋了「為何」某些近似屏障是真實的，而非只是「至今未被打破」。
透過 PCP，MAX-3SAT 變成一個銳利的間隙問題：要分辨「所有子句都能被滿足」的公式與「最多只有 7/8 + epsilon 的子句能被滿足」的公式，是 NP 困難的。任何近似得比 7/8 更好的演算法都會跨過那道間隙、決定一個 NP 困難問題——所以除非 P = NP，7/8 是可能達到的最佳近似。
一個讀常數位元的機率驗證者變成一道難度間隙——從 PCP 通往不可近似性的橋。
PCP 定理並未給出更快「找到」證明的辦法——驗證仍需要完整證明存在。它的力量在於：檢查只需讀 O(1) 個位元，這製造出讓銳利不可近似性結果成為可能的 YES/NO 間隙。