PCP定理的故事

对计算极限的探索何以导致具有超常威力的证明的发现

Dana Moshkovitz (MIT) 著

左  芬       译

【译注：从行文判断，本文大约作于2010年前后。尽管作者已经尽可能写得通俗易懂，读者可能仍然需要一定的知识背景才能读懂。特别地，可能需要知道一点复杂性、近似算法以及纠错码的知识。】

1.   引言

1970年代，算法研究的形势发生了急剧的变化。人们发现，对大量看似平平无奇的算法问题中任何一个的有效算法会导致听起来异想天开的一个结论：给定一个可证明的数学语句，有算法能有效地找出该语句最短的证明。可以这样来看待后者的神奇之处：这样一种算法如果存在的话，眼下至少值六百万美元——由Clay研究所承诺奖励给任何解决六个核心数学问题的人；每个问题一百万美元。有趣的是，六个问题之一正是判定这样一种算法是否存在。该问题被称为P与NP问题。

上述看似平平无奇的算法问题本身看起来很容易就找到近似算法——它们跟那些我们确实知晓有效算法的问题出奇地相似。一个例子是最大割——找出将网络的节点分成两部分的最佳方式，使得其间的链接尽可能多。如果你把“尽可能多”换成“尽可能少”，你就得到最小割，而它基于流的算法直到现在还是所有计算机科学本科生必学的。与此相反，最大割的有效算法会导出价值六百万美元的算法，或者用术语来说，最大割是“NP-难”的。

2.   近似

几年后，研究者们观察到了一些有趣的事情：尽管他们确实没想到诸如最大割这类问题的有效算法，有时候他们能证明某些算法不会比问题的最优解差得太多。例如，这有一种办法来生成最大割问题的一种分割，使得两部分之间的链接数至少是最大值的一半（用术语来说，这是一种“1/2-近似”）：随机选取分割。也就是说，对每个节点抛一次硬币。如果硬币是“国徽”向上，就把节点放到第一部分，而如果硬币是“麦穗”向上，就把节点放到第二部分。一条链接的两个端点分属于不同部分的几率恰好是1/2。因此，平均而言，所有链接中的一半会连接属于不同部分的节点。事实上，对于最大割有一个更好的算法，可以找到一个分割使得不同部分之间的链接数是最优值的0.878倍（亦即，一个0.878-近似）。这一算法由Michael Goemans与David Williamson于 1990年代发现，这里不作介绍。这一算法在过去20年里一直未被改进。

尽管最大割拥有在一个常数因子内的近似，对于其它问题这种近似并没有找到；有时候最好的近似依赖于输入的规模，所以当输入规模变大时，近似就变差了。形成鲜明对比的是，有些问题可以近似到极其好的程度（到0.9999…9以内，有任意个9）。这使得研究者好奇对于其它问题是否也有办法——是否存在更好的近似算法尚未被发现？答案出在了一个始料未及的地方。

3.   近似困难性

到了1990年代早期，研究者认识到了如何证明近似问题是NP-难的。这也就解释了，为何算法家们在试图对某些问题的近似加以改进时鲜有进展。

通往这一突破的观念之路是漫长而错综复杂的。它肇始于10年前，由Goldwasser, Micali与Rackoff在零知识证明上的工作以及Babai在交互式证明上的工作所诱发。那时候，没人预料到这些会对近似算法有所影响，但最终确实如此。

这两项工作提出了证明和校验的新模型，其与写下证明再逐步校验的标准模型完全不同。新模型将定理证明视为证明者与验证者之间的一种讨论。验证者可以问证明者问题，并且问题可以是随机化的。如果验证者对证明正确的合法性认可到了一定概率，比如说0.99，他们就说这足够好了。

这些以及相关的模型接下来成为了研究和分类的主题，进而表现出了惊人的威力。这一研究最终创造出通往近似困难性的专门工具。

4.   稳健证明与PCP定理

-那么什么导出了近似困难性？“仅仅是”如下的定理，只要是写过或者校验过数学证明的人都不会认为它有可能成立，但它事实上却是对的：

“每一个数学证明都可以写成一种格式，使得仅仅阅读两个语句（无论证明有多少个语句）就可以概率性地校验。”

规模为n的标准证明是一系列语句，按1,…,n排序。每一条语句是由前面的某些语句加上前提推导出来的。最后一条语句是我们想要证明的。重要的是，使用标准证明确保最后一条语句正确的唯一方式是逐语句地追踪推理过程。如果在任何一步推导中存在错误，该语句可能就是错的。

与此相反，在新证明格式中，许多语句都可以单独推导出同一语句。比方说，可能位置5的语句决定了位置10的语句，但位置16的语句也决定了位置10的语句。这一结构使得如下的“稳健（robustness）”性质成为可能：哪怕在新格式的所有推导中只有一小部分成立，你仍然能演绎出原始证明的完整推导。

这一稳健性质使得概率性校验成为可能：要校验证明，你选取一对随机的位置，使得第一个位置的语句应该能推导出第二个位置的语句。对于正确的证明而言，第一条语句确实导出第二条。而相反，如果证明的要旨就是错的，亦即没有论证可以导出它，那么几乎所有推导应该都不成立。于是，第一条语句导出第二条的概率会很低。

这一定理被称为PCP定理，其中PCP指代“概率性可校验证明（Probabilistically Checkable Proofs）”。

巧合的是，或许一些读者也发现了，PCP也指代“苯环己哌啶（Phenylcyclohexyl Piperidine）”，一种取乐解离药物。据参与PCP早期版本之一的研究者Muli Safra称，这一名称是用来纪念一次事故的，当时警察误以为Safra和他的朋友在运作一个PCP实验室。Safra觉得他们被错误指控后唯一能做的就是真正运作一个PCP实验室（尽管其本质不同）。

5.   PCP定理如何导出近似困难性

为了完成这一拼图，让我先解释PCP何以关联到近似困难性【原注：这一解释是自我完备的，但没有任何NP-难方面背景的读者可能难以跟上。】

假定你想要证明最大割的0.95-近似的困难性。我们声称，只要你能证明如下命题就够了：给定一个网络，对以下两种情形予以区分是NP-难的：一种情形是存在节点到两个集合的一种分割，使得所有链接的X比例在不同部分之间；而另一种情形是，在节点到两个部分的每个分割里，链接的至多Y比例是在不同部分之间，而Y/X=0.95。为何说这样就够了？因为如果你能够近似两个部分的最大链接的比例到0.95以内，你就能够区分这两种情形。由于比例X和Y之间存在间隙，这一区分问题通常被称为间隙问题。

接着你想要展示间隙问题跟测试给定数学语句是否存在规模n的证明一样难，因为这就表明0.95-近似最大割是NP-难的。这是通过规约的方法来完成的：给出一种有效的方法将测试问题转变为间隙问题，于是间隙问题的有效算法就导出测试问题的有效算法，进而意味着间隙问题至少跟测试问题一样难。具体来说，你把一条数学语句以及问题“是存在一个规模至多n的证明，还是每个证明都需要大于n的规模？”转变为一个网络以及问题“是存在将网络节点分割成两部分的一种方式使得不同部分的链接比例至少是X，还是最好的分割也只拥有至多Y-比例的链接？”

假定你的规约是正确的，那么数学语句的一个规模n的正确证明会转变为网络节点的一个分割，其中至少X-比例的链接在两个部分之间。于是证明的这一新格式成为对节点到“第一部分”或“第二部分”的一种指派。有趣的是，为了校验新证明，随机选一条链接并校验其端点是否在不同部分（亦即，第一个端点在第一部分导出第二个端点在另一部分）足矣。一个正确的证明确保正确推导的概率至少是X，而错误证明确保推导概率至多是Y。总而言之，从“是否存在一个规模n的证明”到间隙问题的规约本质上等价于从证明到概率性可校验格式的转换。换句话说，它就是一种PCP定理。

这一PCP定理跟我们此前描述的稍有不同：否决【译注：原文如此。应为接受。】一个正确证明的概率，X，不是1。此外，尽管接受一个错误语句的证明的概率Y比X要低，它可能不会比X低太多。这些都是使用“最大割测试”校验证明带来的人为产物。如果我们改变允许的测试类型，有办法将否决一个正确证明的概率降为0，同时让接受错误语句的证明的概率接近0。

6.   PCP定理的证明

PCP定理在证明起来困难且繁复这一点上声名狼藉，而这，在作者看来，是不成立的。在这一节中我们会勾勒出这一证明。勾勒的目的是获得对证明的感知，而不是给出所有的细节。因此，我们会时常跳过技术细节，并忽略对有些环节的深入解释。

PCP定理的证明过程会不断地缩减证明中需要阅读的语句数，使得它最终从n（所有语句）降到2。以下我们仅描述一次缩减，而它接着可以递归地作用。这一递归，在PCP行话里称作“复合”，有些棘手，并且尽管我们如今知道有更巧妙的方式去执行它，这些方式会带来参数上的显著损失。我们在这次介绍中略过复合的细节。

我们假定一种证明格式，以及阅读证明中q条语句的一个概率性验证者。我们刻画一种新的证明格式以及阅读远小于q条语句的一个概率性验证者。这一新格式是对现存证明的一种编码，采用的是纠错码理论中所谓的Reed-Muller码。这一编码是一种代数 码——它的定义涉及有限域以及多变量多项式。对第一次遇到这种构造的读者来说这可能看起来有点出乎意料，不过其实有大量数学论证的例子，它们跟多项式没什么关系，但最终多项式都在其中派上了大用场。

考虑有限域，令为域中少量元素的集合，使得对于某个参数，。Reed-Muller码将有限域上的一个-变量低次多项式内插于现存证明，并将现存证明的比特诠释为多项式在子集积上的取值。这一新格式还包含一些辅助数据，后面将解释。使用低次多变量多项式有两个目的：首先，它们构成一种纠错码，意味着从一个多项式移动到另一个得改变中大多数点的值；其次，它们具有递归结构：将一个多项式约束到更少的变量，给其它变量赋值，仍然是一个低次多项式。

你可以证明（我们这里略去细节），不失一般性，验证一个证明只需要校验上某种低次多项式之和为零即可（并不就是Reed-Muller多项式，但依赖于它以及给定的验证者）。注意初看起来你需要阅读证明中的个位置以校验其和，就好比你需要阅读证明中的条语句以校验它。我们将说明仅仅阅读个位置就够了！我们实现的方式是在新证明格式中添加辅助数据。

这些辅助数据是我们想要校验的求和的“部分和”。部分和固定前个坐标，并仅对剩余坐标求和：

在证明的新格式中，我们会对所有以及中的所有存储（表格）。

基于定义，部分和彼此相关，且与相关。它们满足的准确方程是这些：

1.   

2.  

3.   

   下面我们刻画验证者。验证者首先校验表格都是（近似）低次多项式。这可以通过阅读在一条随机直线上的值来完成，并被称为“低次测试”。如同我们上面提到的，低次多项式有一条惊人的性质：两个不同的低次多项式在几乎所有点上都不同。因此，3中的等式可以在单个随机点上概率性地进行校验，而2中的个等式每个可以在个点上概率性地校验。至于等式1，它使得所有个点上的求和得以校验。质询的总数是，而不再是。质询数上的大幅节约是通过部分和执行的预计算而成为可能的。重要的是，这一预计算可以利用递归结构和多变量多项式的编码性质予以校验。

2005年，Dinur基于扩展图（Expander）发现了PCP定理的一个不同以往的美妙证明。这一证明只能给出很高，比方说0.999，的错误概率，而上面勾勒的证明则截然不同，可以给出非常低的错误概率。当然这一错误概率可以接着用其它方法去降低。

7.   最优困难性结果

尽管PCP定理在1990年代早期给出了首个近似困难性结果，直到大约1997年这类困难性结果才跟各种问题已知的最优近似符合上。

从PCP定理得到最优困难性结果的过程通常由以下步骤组成：

1.     可靠性放大：当PCP定理具有很高的错误概率时，你首先得降低这一概率。这通常要用到Raz（1994）给出的并行重复引理，其证明基于信息论的思想。

2.     利用Bellare-Goldreich-Sudan（1995）的一种特殊构造，将PCP与“长码”复合起来，这样就可以针对特定的近似问题定制PCP了。

3.     利用Fourier分析对长码加以分析，如同Håstad（1997）首次做的那样。这一分析依赖于PCP的低错误。

8.   独一游戏猜想

那么近似最大割到底有多难？Håstad说明近似最大割到好于16/17≈0.941是NP-难的。是否存在比Goemans-Williamson≈0.878-近似更好的算法？我们并不知道。不过，如同理论计算机科学里司空见惯的那样，我们可以对我们的知识现状做一个“Rumfeld式”【译注：即Donald Rumfeld所谓“已知的已知”、“已知的未知”及“未知的未知”分类。】的论断：如果不存在的话，我们可能知道如何得知。

2002年Khot提出了独一游戏猜想（Unique Games Conjecture，UGC），其中假定了一种特殊PCP的存在性，下面会加以解释。UGC如果对的话，就解决了最大割的近似可能性，并确定Goemans-Williamson算法为最优 [Khot-Kindler-Mossel-O 'Donnell, 2004]。如果它对的话，UGC还会解决大量其它问题，包括涉及覆盖、分割及排序的NP-难问题。除此之外，这一猜想还表明，一种特定的算法技术，所谓“半正定规划”，会给出最优的近似算法 [Raghavendra, 2008]。

什么是独一游戏猜想？这里的“独一”指的是校验双向推导而不是单向推导：位置1处的语句会导出位置2处的语句，而同时，未知2处的语句也会导出位置1处的语句。看起来仅仅使用这种当且仅当不太可能校验任何证明。然而，独一游戏猜想表明这是可能的——至少当你能使用一个有趣的花招时：哪怕在一个正确的证明中也有微小比例的当且仅当允许出错。这使得独一验证成为可行的，而猜想就是这样一种验证过程可以达到任意低的错误几率。

从最大割获得的PCP是独一的：如果将节点分割成两个部分，使得至少X比例的链接在两部分之间，那么对于所有连接，除了至多1-X比例以外，链接的一个端点在一部分当且仅当另一个端点在另一部分。独一游戏猜想说明可以获得非常低的错误概率，只要你将最大割加以推广，使得有很多个部分，而非仅仅两个。

9.    更多未解问题

哪怕独一游戏猜想解决了，还会有其它未解的问题。例如，在旅行商问题中，一个旅行商想要游遍给定的目的地并最小化费用，对此我们甚至没有备选的方法用于证明紧的近似困难性结果。

而关于原始的PCP定理，大量有趣的未解问题仍然存在。目前，我们对这一定理所知道的最低错误概率（对于本文介绍的“两质询投影”版本）随着证明规模对数式地变小 [M-Raz 2008]。你可能先验地希望能有多项式那么小的错误（“投影游戏猜想”/“尺度下行猜想”）。另一个未解问题是最小化概率性校验格式带来的膨胀：通过2000年代完成的研究，我们知道证明格式的规模不必增长超过一个次线性因子就可以使得该格式概率性可校验。一个常数因子的增长是否就足够了呢？

另一个问题是PCP是否能用到实践中。我们如今知晓的小型膨胀、低错误概率以及概念上更简单的构造可能导致一种实用“PCP技术”。它在什么时候会有用呢？这需要一种非对称场合，其中证明者愿意投入更多额外的工作来准备证明，而验证者需要极其高效。验证者可能不信任证明者，并且必须确定证明者交付了证明，比如把它写下来。你可以想象这类条件成立的场合——例如一台服务器和一些弱代理。

10.  引文说明与延伸阅读

PCP定理的首个证明由Arora-Safra和Arora-Lund-Motwani-Sudan-Szegedy完成于1992年。带有更多质询数目的稍弱一些的PCP定理此前就已出现，由Lund-Fortnow-Karloff-Nisan、Babai-Fortnow-Lund以及Babai-Fortnow-Levein-Szegedy等工作给出。证明的局域校验与近似困难性的关联首次出现于Feige-Goldwasser-Lovász-Safra-Szegedy 1991年的工作中。Papadimitriou和Yannakakis给出了一族难以近似的备选问题。在PCP定理被证明后，Lund与Yannakakis提供了进一步的困难性结果。后续发展的引文在正文中已给出。

有很多关于PCP定理的讲义和综述。特别地，作者本人也讲过一门关于PCP的课程，讲义可在她的主页上获得。

转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。

链接地址：https://wap.sciencenet.cn/blog-863936-1493370.html?mobile=1

收藏

分享