PCP - Probabilistic Checkable Proof

作者:, 发表于

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

作者:yijia

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

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

  1. \(V\) 有两个输入 \(x\)\(y\) ,并且 \(|y|=poly(|x|)\)
  2. 对于任意的 \(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.


上一篇:高等理论计算机I2008年9月19日
姚期智教授给清华大学新入学研究生开的一门课,课程内容 在经典计算复杂性方面:NP完全性,多项式空间复杂性,对数空间复杂性,交互式证明系

下一篇:为什么这个世界需要量子机制2008年11月21日
注:这学期姚期智先生在清华给了一门研究生课程《高等理论计算机I》,主要内容就是讲量子计算,我也许诺要写一些这方面的东西,现在这门课已经


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。