PCP Theorem 序0

來自專欄 演算法小記

這學期上了一下學校的計算複雜度理論（Computational Complexity）。由於課上只剩下了6個人，所以James決定取消Final，然後讓我們六個人一起講一遍PCP (Probabilistic Checkable Proof) Theorem的證明 ( Irit Dinur 的版本） 我決定把它整理一下，然後掛在這裡。

閱讀本系列文章，需要一些關於複雜度理論的基礎知識，雖然我感覺PCP theorem本身也算基礎知識XD.

我估計文章會分為如下幾個部分：

1. PCP Theorem的介紹
2. PCP Theorem 和 的等價
3. Expander 圖的介紹以及它的基本定理
4. Irit Dinur 證明的概述
5. Constraint Graph和Degree Reduction
6. Gap Amplification
7. 字母表規約 (Alphabet Reduction)

本文基本上會按照我校05年Venkatesan Guruswami 和 Ryan ODonnell的notes的順序來講。

歡迎大家提出任何證明和翻譯上的問題。

P.S. @圓角騎士魔理沙 也在課上！

推薦閱讀：