PCP - Probabilistic Checkable Proof

作者: , 共 2744 字 , 共阅读 0

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