PCP 定理（probabilistically checkable proofs，機率可檢查證明）
/ P-C-P /
想像一份一千頁的數學證明。為了確認它正確，你通常得逐行讀完。PCP 定理提出一個聽來不可能的主張：有一種方式可以把任何證明重寫，使你只讀其中極少數、隨機挑選的符號，就能幾乎確定它有效。抽查三頁，若證明有誤，你會以不錯的機率逮到錯誤；再多讀幾頁，你的信心便壓倒性地高。
用複雜度的語言陳述，PCP 說：NP 裡的每個問題都有一種證明格式與一個驗證者，後者只用常數個隨機擲硬幣、只讀證明中常數個位元，卻同時滿足完備性（真主張有一份驗證者永遠接受的證明）與健全性（對假主張，任何聲稱的證明都以至少 1/2 的機率被拒絕）。訣竅在於證明被編碼得極為穩健，任何瑕疵都被抹散到整份文件——你無法造出一份在幾乎每個局部都一致的錯誤證明，所以少數幾次隨機探測，極可能命中那散佈開來的謊言證據。用符號寫：NP = PCP(O(log n), O(1))——對數個隨機位元、常數個查詢。
除了是關於證明的驚人事實，PCP 定理還是近似困難性的引擎。那穩健的編碼製造出一道「缺口」：真實例幾乎完全可滿足，而假實例無法被滿足到超過某個比例。一個把最佳值近似得很接近的演算法將能區分這兩者，從而精確地解出底層的 NP 完全問題——所以好的近似將迫使 P = NP。幾乎每個現代不可近似結果，從 MAX-3SAT 到圖著色，都源自 PCP 定理。這是一個深刻、得來不易的結果（1990 年代初被證明，後來由 Dinur 給出組合式證明）。
想像把一個是非答案編碼成的不是一個位元，而是一個散佈在數千位元上的長糾錯碼字。若證明者寫下錯誤答案，編碼會迫使碼字中極大比例變得「不對」，所以一個只抽樣少數幾個隨機位置的驗證者，幾乎必然落在某個錯誤位元上而拒絕——根本不必讀完整份。
PCP 把證明重寫成「任何錯誤都散佈各處」；少數幾次隨機抽查就能逮到謊言。
PCP 並不能讓你只讀幾個位元就檢查任意的普通證明——證明必須先被重新編碼成穩健的 PCP 格式。而健全性是機率性的：單一輪以至少 1/2 的機率逮到假證明，重複則把它放大到趨近確定。