PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一，它给了NP 问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
作者： yijia
我们可以从最基本的 NP 开始。一般 NP 的定义是基于 nondeterministic Turing machine ，但我们也可以用类似于 Interactive Proof 的系统来刻画：
一个语言$ Q$ 是在 NP 内当且仅当存在一个多项式时间的算法$ V$ (i.e., prover) 满足下面一系列条件：
- $ V$ 有两个输入$ x$ 和$ y$ ，并且$ |y|=poly(|x|)$ ；
- 对于任意的$ x$ ， 我们有
2.1. 如果$ x \in Q$ ，那么存在一个$ y$ 使得$ V(x,y)=1$ ， i.e., $ V$ accepts $ (x,y)$ ;
2.2 如果$ x \not\in Q$ ，那么对于任意 y 都有$ V(x,y)=0$ ， i.e.,$ V$ rejects $ (x,y)$ .
在 2.1 中，$ y$ 可以看成是$ x \in Q$ 的一个证明。对于 3Sat 问题，我们可以设计这样的$ V$ : $ x$ 是一个 3CNF 公式，而 y 是一个对$ x$ 中所有变元的赋值。Prover $ V$ 就是用来验证 y 是否满足 x。直观上$ V$ 必须读完整个$ y$ 才能确认$ x\in Q$ 。 那么有没有可能改进这一点，让$ V$ 只读$ y$ 的一部分，来增加效率? 比如现有的 Graph Minor Theory 的证明有几百页，如果只要其中几页就能确认其正确那么就会省去 Reviewer 的很多时间。如果$ V$ 是个确定时间的算法，这就等价于要求$ |y|=o(|x|)$ 。那么如果每个 NP 问题都有这样的 Prover ， 我们就可以证明 NP 包含 Subexponential Time 里。一般公认这不可能成立。
但如果我们允许$ V$ 使用 Randomness ，问题就开始变得有趣了。这也就是 Probabilistic Checkable Proof (PCP)。
要定义一个 PCP 系统, 我们先要给定两个函数$ r,q: N \rightarrow N$ 。我们说一个随机算法$ V$ 是一个(r(n),q(n))-restricted verifier, 如果$ V$ 在输入$ (x,y)$ 上使用$ O(r(|x|))$ 位随机数，访问$ y$ 的$ O(q(|x|))$ 位。直观上， V 扔了$ O(r(|x|))$ 个骰子，然后根据结果去访问证明 y 的$ O(q(|x|))$ 位。 当然 V 还要是一个多项式时间算法，$ |y|=poly(|x|)$ ， 同时满足所谓的 non-adaptive 条件（写起来太罗嗦了，所以就不写了)。
我们说这样的$ V$ 定义了一个语言$ Q$ 当且仅当对于任意的$ x$ ， 我们有
(a) 如果$ x \in Q$ ，那么存在一个 y 使得$ Pr[V(x,y)=1]=1$ ;
(b) 如果$ x \not\in Q$ ，那么对于任意 y 都有$ Pr[V(x,y)=1]<1/2$ .
要注意的是并不是所有的$ V$ 都定义了一个语言，因为(b)不是总能满足的。
非常壮观的 PCP 定理就是
Theorem 1. NP=PCP($ \log n,1$ )
也就是说，对于每个 NP 语言我们都可以构造一个$ V$ ，在每个$ (x,y)$ 上，仅使用$ O(\log|x|)$ 位随机数，访问证明$ y$ 中的常数多位，就能以很高的概率正确判断是否$ x \in Q$ 。
由于可以证明 PCP($ \log n,1$ )对于多项式时间规约(PTIME reductions)封闭，所以 PCP 定理也可以叙述为
Theorem 2. 3Sat $ \in$ PCP($ \log n,1$ )
除了本身非常有趣和 counter intuitive ， PCP 的一个重要应用就是近似算法的下界:
Corollary. 如果 NP$ \ne$ P, 那么 Max-3Sat 没有 PTAS ，同时 Max-Clique 不存在 constant approximation。
这个结论的证明就是通过 PCP ，构造所谓的 Gap Instances ：给定常数$ \delta \in (0,1)$ ，$ Gap_\delta$ -3Sat 是如下的问题
input: 一个 3CNF 公式$ x$ 使得要么存在一个满足$ x$ 的赋值，要么所有的赋值最多满足$ \delta$ -fraction 的 clauses。
question ：$ x$ 是否可满足？
Corollary 3. 存在一个$ \delta$ ，使得存在一个 3Sat 到$ Gap_\delta$ -3Sat 的规约。
实际上我们可以证明
Theorem PCP 定理成立当且仅当上面的 Corollary 成立。
现在 PCP 定理有两个证明：一个就是由 Arora ， Sudan 等人在 90 初完成的基于代数的方法，直接证明 Theorem 2。证明的核心某种意义上就是 Error Correcting Code。另一个就是 Dinur 前几年完成的基于 Expander 的组合方法，直接证明 Cororllary 3。前者的证明很长，但实际上比较初等，而后者短一些且非常漂亮。
Q. E. D.
