PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一，它给了NP问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP介绍。

作者：yijia

我们可以从最基本的NP开始。一般NP的定义是基于nondeterministic Turing machine，但我们也可以用类似于Interactive Proof的系统来刻画：

一个语言是在NP内当且仅当存在一个多项式时间的算法  (i.e., prover) 满足下面一系列条件：

1. 有两个输入和，并且；
2. 对于任意的， 我们有
   2.1. 如果，那么存在一个使得，i.e., accepts ;
   2.2 如果，那么对于任意y都有，i.e., rejects .

在2.1中，可以看成是 的一个证明。对于3Sat问题，我们可以设计这样的: 是一个3CNF公式，而y是一个对中所有变元的赋值。Prover 就是用来验证y是否满足x。直观上必须读完整个才能确认。 那么有没有可能改进这一点，让只读的一部分，来增加效率? 比如现有的Graph Minor Theory的证明有几百页，如果只要其中几页就能确认其正确那么就会省去Reviewer的很多时间。如果是个确定时间的算法，这就等价于要求。那么如果每个NP问题都有这样的Prover， 我们就可以证明NP包含Subexponential Time里。一般公认这不可能成立。

但如果我们允许使用Randomness，问题就开始变得有趣了。这也就是Probabilistic Checkable Proof (PCP)。

要定义一个PCP系统, 我们先要给定两个函数。我们说一个随机算法是一个(r(n),q(n))-restricted verifier, 如果在输入上使用位随机数，访问的位。直观上，V 扔了个骰子，然后根据结果去访问证明y 的位。 当然V还要是一个多项式时间算法，， 同时满足所谓的non-adaptive条件（写起来太罗嗦了，所以就不写了)。

我们说这样的定义了一个语言当且仅当对于任意的， 我们有
(a) 如果，那么存在一个y 使得;
(b) 如果，那么对于任意y都有.

要注意的是并不是所有的都定义了一个语言，因为(b)不是总能满足的。

非常壮观的PCP定理就是

Theorem 1. NP=PCP()

也就是说，对于每个NP语言我们都可以构造一个，在每个上，仅使用位随机数，访问证明中的常数多位，就能以很高的概率正确判断是否。

由于可以证明PCP()对于多项式时间规约(PTIME reductions)封闭，所以PCP定理也可以叙述为

Theorem 2. 3Sat PCP()

除了本身非常有趣和counter intuitive，PCP的一个重要应用就是近似算法的下界:

Corollary. 如果NPP, 那么Max-3Sat没有PTAS，同时Max-Clique不存在constant approximation。

这个结论的证明就是通过PCP，构造所谓的Gap Instances：给定常数，-3Sat是如下的问题

input: 一个3CNF公式使得要么存在一个满足的赋值，要么所有的赋值最多满足-fraction的clauses。
question： 是否可满足？

Corollary 3. 存在一个，使得存在一个3Sat到-3Sat的规约。

实际上我们可以证明

Theorem PCP定理成立当且仅当上面的Corollary成立。

现在PCP定理有两个证明：一个就是由Arora，Sudan等人在90初完成的基于代数的方法，直接证明Theorem 2。证明的核心某种意义上就是Error Correcting Code。另一个就是Dinur前几年完成的基于Expander的组合方法，直接证明Cororllary 3。前者的证明很长，但实际上比较初等，而后者短一些且非常漂亮。