青春的岁月，我们身不由己: PCP - Probabilistic Checkable Proof

Sent to you by iveney via Google Reader:

PCP - Probabilistic Checkable Proof

via 阅微堂 by zhiqiang on 10/19/08

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

作者：yijia

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

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

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

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

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

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

我们说这样的定义了一个语言当且仅当对于任意的，我们有
(a) 如果 $x \in Q$ ，那么存在一个y 使得 Pr[V(x,y)=1]=1 ;
(b) 如果 $x \not\in Q$ ，那么对于任意y都有 Pr[V(x,y)=1]<1/2 .

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

非常壮观的PCP定理就是

Theorem 1. NP=PCP( $\log n,1$ )

也就是说，对于每个NP语言我们都可以构造一个，在每个 (x,y) 上，仅使用 $O(\log|x|)$ 位随机数，访问证明中的常数多位，就能以很高的概率正确判断是否 $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公式使得要么存在一个满足的赋值，要么所有的赋值最多满足 $\delta$ -fraction的clauses。
question：是否可满足？

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

实际上我们可以证明

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

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

高等理论计算机I
姚期智教授给清华大学新入学研究生开的一门课，课程内容在经典计算复杂性方面：NP完全性，多项式空间复杂性，对数空间复杂性，交互式证明系...
Windows游戏中的NP完全问题
上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌...
扫雷是NP完全问题
本科时有同学扫雷最快可以在60多秒完成高级难度，让我这种最快130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才...
素数筛法的复杂度
Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。所谓素数筛法就是那个求小于n的...
TCS：NP-hard
好久没有写我的理论计算机初步系列了，其实复杂性这一块，虽然平时经常遇到，但由于问题都过于本质和困难，想这方面问题的时间反而不多。Ko教...

Things you can do from here:

Subscribe to 阅微堂 using Google Reader
Get started using Google Reader to easily keep up with all your favorite sites

青春的岁月，我们身不由己

Thursday, October 30, 2008

PCP - Probabilistic Checkable Proof

Sent to you by iveney via Google Reader:

PCP - Probabilistic Checkable Proof

相关文章

Things you can do from here:

No comments: