PCP - Probabilistic Checkable Proof

作者: , 共 2480 字

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.

类似文章:
相似度: 0.142
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
相似度: 0.083
姚期智教授给清华大学新入学研究生开的一门课,课程内容:
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
碎碎念 » 找工作, 营销
via 宣传 & washingtonpost
数学 » 物理
今天水木十大有一个很搞笑的题目。大家来看看,如果单凭直觉你会选什么?