精选
PCP定理史
Ryan O 'Donnell 著
左 芬 译
【译者按：概率性可校验证明（Probabilistically Checkable Proofs，简称PCP）定理在某种意义上代表着经典复杂性理论的巅峰。当前，量子复杂性理论正处在蓬勃的发展阶段，并且取得了MIP*=RE这样振奋人心的成果。通过了解PCP定理的发展史，或许会对我们发展量子复杂性理论有所帮助。因此，我们把这篇有趣的简史翻译出来，供大家参考。本文需要一定的复杂性理论基础方能读懂，在此预先提醒一下。考虑到本文并未给出太多细节，译者会在将来收集一些更详实的文章，以飨读者。】
【作者前言：在我本人，Ryan O 'Donnell，的设想里，这会是对PCP定理史的一份附有照片的简要记录。我的主要信息源是Babai的文章《电邮与交互的超常威力》，Goldreich的文章《证明体系一览》，以及一手信息。很可能会有不少含糊和缺失的地方，我在这里对此先行道歉并征求更正。由于这一短文是为华盛顿大学的一门课程准备的，跟华盛顿大学有关的一些细节会着重指出。】
在Irit Dinur（2005年4月）给出PCP定理激动人心的全新证明之后，关于PCP定理的课程就不再需要深入到原始证明里繁复——如果说是这样的话——细节里了。但这一原始证明以及得出它的七年努力仍然是一段有趣的历史，相当值得一听。
Irit Dinur
PCP定理的故事是1980年代从麻省理工学院开始的，起源于获得史上首届Gödel奖的一篇论文：《交互式证明体系的知识复杂性》，作者是Goldwasser, Micali与Rackoff。这篇文章最初发表于STOC '85，
【译注：STOC是ACM Symposium on Theory of Computing的简称，即由美国计算机协会（ACM）举办的计算理论年度研讨会。】
可是据说早在82年末它的草稿就已经出现了；确实，据传它至少在83年的一篇文章中就被引用了。传言这篇文章曾被FOCS '83，
【译注：即Symposium on Foundations of Computer Science，计算机科学基础研讨会。】
STOC '84以及FOCS '84拒稿了，尽管不清楚在这些被拒的情况下该文有哪些内容。
Shafi Goldwasser Silvio Micali Charlie Rackoff
Goldwasser，Micali与Rackoff真正感兴趣的是证明某件事情在哲学层面上的含义，尽管他们文章的主要动机是加密。该文引入了两个全新的概念：交互式证明，以及零知识证明。
定义 1 在交互式证明中，一个携带私密硬币抛掷结果的概率性多项式时间验证者与一个全能证明者交互；它们之间会来回传送多项式轮次的消息。正确的断言应该有以概率“1”（“完备性”）被接受的证明，而错误的断言应该以至少1/2（“可靠性”）的概率被否决，不管证明为何【原注：事实上，GMR最初允许完备性为
；这其实无关紧要。】。我们用IP表示这类交互式证明语言。
这是GMR所能想到的，有效证明最一般的概念；他们是用课堂上老师向学生出示证明这样一个场景来建模出它的。至于他们提出的另一个概念，零知识证明，我们在这里不会涉及太多细节。我们只提及一点，在传统证明里你除了知晓定理为真这一事实外，还会“学到”它的许多内容，而在交互式证明里可以做到除了知晓定理为真之外，你学到“零额外信息”。GMR的主要实例是“二次非剩余”问题。不难在NP中证明一个数是二次非剩余的，只需将模数的分解作为证据即可；可是这揭示了很多信息。GMR给出了这一事实的一个“零知识”证明。这当然是零知识证明的一个有趣案例，但就交互式证明而言却不然，因为这一问题已经在NP内了。
独立于GMR，且发表在同一期STOC '85上的，是Babai的一篇文章，《用群论换取随机性》。这篇文章后来以期刊版发表时题为《Arthur-Merlin游戏：一种随机性证明体系，以及复杂性类别的一个层级》，并增加了Moran为共同作者；事实上，这篇文章与GMR分享了史上首届Gödel奖。
Laci Babai Shlomo Moran
Babai此前跟Szemerédi合写过一篇文章，在其中他证明某些特定的群论问题——例如，由生成元给出的有限域上的矩阵群，它的阶是否至多 
？——在NP内，但受限于某个未证明的群论猜想。
Endre Szemerédi
Babai想要得到一个无条件结果，于是他独立地引入了交互式证明的概念，尽管用的是公开 硬币抛掷，并且证实他的问题具有常数轮次的交互式证明。特别地，他给出了以下定义：
定义 2 AM[k]是具有
个轮次的一类交互式证明，其中验证者先说话，且持有公开的硬币抛掷结果。（AM代表Arthur-Merlin，Arthur是验证者，而Merlin是证明者。）
Babai接着证明：
定理1 对于所有常数 ，AM[]=AM[2].
AM[2]类如今被直接称为AM。在这一定义下我们看到AM[poly]跟IP非常相似：主要的差异是公开硬币与私密硬币。Goldwasser与Sipser此后不久（STOC '86）证明它们其实是同一类。于是在这篇文章后，IP这样一个良好的、稳健的类别就被定义好了，并且看起来刻画了有效证明语言的一个宽泛的概念。
Mike Sipser
事实上，这一类别很快就把复杂性理论家们迷住了，原因如下：GMR的交互式证明是针对已经在NP内的问题的。Babai的证明是针对他猜测在NP内，但没有足够的群论手段来证明的问题。可是在FOCS '86（事实上，这一结果比Goldwasser-Sipser早一点公布出来。）上，Goldreich、Micali与Wigderson证明图不同构问题在IP内，而该问题人们早就考虑过，并花了相当长时间想要放到NP里。
定义 3 图不同构是图同构的补：给定 
与
，以邻接列表给出的两个图。它们是否同构？亦即，是否存在顶点的重命名，使得它们是相同的图？
定理 2 （GMW '86）图不同构在IP内。
证明：验证者随机选取
，随机置换
的顶点，将所得图呈现给证明者。证明者需猜出
。对于完备性，如果图是非同构的，那么全能证明者肯定能识别 。对于可靠性，如果图是同构的，那么不管是多少，证明者会在两个图上看到同样的概率；因此它所能做的只有猜测。 □
Oded Goldreich Avi Wigderson
此后一小段时间里没有什么关于IP的重要进展，尽管交互式证明持续受到加密界的关注。特别地，在STOC '88上，为了从关于零知识证明的一些结果中去除加密的假定，Michael ben-Or，Goldwasser, Joe Kilian与Wigderson引入了多方交互式证明的概念：
定义 4 （BGKW '88.）MIP是拥有多个不交流证明者的交互式证明类。
BGKW的一个定理表明拥有多项式个证明者的MIP跟拥有两个证明者的MIP是同一类。
Miki Ben-Or Joe Kilian
又过了稍长的一段时间，交互式证明的复杂性依然风平浪静。Babai猜测过IP=AM，并且确实看起来大多数人都相信IP（甚至MIP）仅仅是NP的一个稍微随机化的推广。从哲学的视角来看，这似乎是高度合理的：从有效证明概念的这样一个合理推广中，为什么你会期待显著的额外威力呢？Fortnow与Sipser在88年证明，存在一个谕示（oracle），相对于它coNP不在IP内；同年Fortnow，Rompel与Sipser将这一结果推广到MIP。（这篇文章也给出了MIP的另一种定义，其中采用的证明校验方法后面将会很有用……【译注：可以推测，这里指的是利用交叉质询的原理随机查阅证明者之一给出的内容。】）因为这一谕示性结果，对类似比方说coNP
MIP这类结果的证明将需要此前从未在复杂性理论中见过的一种证明技术（具体来说，一种非相对性技术）。这很成为一种“情感障碍”，如同Babai之后所写。
Lance Fortnow John Rompel
于是，当Nisan在1989年11月27日发电子邮件
【原注：提醒一下，1989年的电子邮件。Babai的祖国匈牙利直到1990年3月才有电子邮件。】
给一些同行，说明积和式（Permanent）进而非常庞大的类P#P
⊇PH在MIP内
【原注：结果P#P⊇PH在1989年早些时候由Toda证明。译者补注：关于PH，P#P，Toda的证明以及更多相关内容，可参考D.J.A. Welsh所著的“Complexity: Knots, Colourings and Counting”第一章。】
时，所有人一定都震惊了。Nisan接着跑到南非去度假了。应该注意到，他的文章基于1989年已经在传阅的一些前期工作，包括M. Blum和S. Kanna在程序校验上的，Lipton在积和式的随机自规约上的，以及Beaver和Feigenbaum在谕示和代数编码上的。
Manuel Blum Sampath Kannan Dick Lipton Donald Beaver Joan Feigenbaum
Nisan的结果非常惊人，不过也有一些人质疑MIP的相关性——尽管IP作为有效证明的概念听起来甚为合理，MIP则看上去并不明朗。两周后事情就急转直下了；12月13日，Fortnow代表芝加哥三人组（Karloff与Lund）给数十个同行发了封邮件，其中附上了积和式进而P#P在IP内的证明的LATEX文件。这无疑相当惊人，因为它意味着IP比人们此前意识到的要强大相当之多。不仅仅coNP在其中，整个多项式时间层级都在其中。关于Fortnow邮件收件人的旁注：华盛顿大学教授Martin Tompa在名单中，并且在我看来很可能华盛顿大学教授Richard Ladner也在名单中。如Babai所写，明显不在名单中的有Razborov以及任何东欧的同行。注意柏林墙才刚在一个月前倒下（11月9日），而苏联仍然还将存续一年半。另一个旁注，关于这一结果的功劳认定，Lund被定为文章的“第一作者”，无视按字母排序的标准做法，因为他显然想出了证明的关键步骤。Fortnow后来写道，他认为这个决定不妥【原注：见http://weblog.fortnow.com/archive/2003 12 07 archive.html】。此外，Nisan也被列为文章的共同作者。因此这一结果的功劳认定通常是：
定理 3 （LFKN '90）P#P⊆IP.
可是人们早就知道IP⊆PSPACE（这一结果通常被归功于P. Feldman '86，尽管我也看到有人把它归功于Papadimitriou '83年关于《对抗自然的游戏》一文。）；显然在这封邮件之后竞赛发展为证明相反的包含关系。这在两周后就完成了：Shamir在1989年12月26日发出一封邮件，在其中他引入了一些全新的巧妙技术证明：
（注意这一IP=PSPACE成果有时也被归功于LFKN+Shamir。）
为了不被落下，三周后（1990年1月17日）另一封邮件由Babai，Fortnow与Lund发出：
定理 5 （BFL '90）MIP=NEXP；亦即，任何指数规模的证明都可以在多项式时间通过多个证明者实现。
这一阵工作算是产生了一个自然的终结点。定理IP=PSPACE如今被视为复杂性理论的杰作，它神奇地刻画了何为有效证明。而MIP=NEXP定理如今则被认为有些晦涩难懂，但它后来实际上激发了PCP理论的几乎全部未来发展。（顺便说一句，这一系列工作也在某种程度上激励了去随机化理论的很多未来发展，通过Babai, Fortnow, Nisan以及Wigderson的一篇文章。）
这些成果出来不到一年，人们就开始试着将其“缩减”到NP上；亦即试着对验证者的能力加以限制，进而重新刻画可证明的传统概念。早期的限制之一是约束验证者对空间的使用。这一方向上的大部分工作都是Condon完成的，她1987年在华盛顿大学的博士论文因为在游戏和交互式证明方面的研究获得了美国计算机协会授予的博士论文奖。
Anne Condon
Condon早期在STACS '91【译注：STACS全称为International Symposium on Theoretical Aspects of Computer Science，即计算机科学理论国际研讨会。】的一篇文章中的一个结果尤其有趣。在该文中她证明NP正好是验证者只有对数空间和对证明的单向阅读权时的交互式证明语言类。（对此结果的一个技术性改进之后由Condon和Ladner得到。）主要的证明工具源于IP=PSPACE结果。可是除此之外，该文作为推论说明，矩阵的最大-单词问题（给定矢量
，矩阵
，以及，最大化
）没有常数因子近似算法，除非NP=P。这是有史以来首个交互式证明与近似困难性之间的关联。不过，可惜的是，Condon的结果并没有获得太多的历史认可，因为让验证者空间受限事实上并不是最有产出的约束方式。
另一种约束考虑限制验证者的时间。Babai, Fortnow, Levin和Szegedy 1991年早中期的一个结果表明如果证明者被强制将证明以某种纠错码写出来，那么所有NP语言都可以被具有多对数时间的验证者校验。BFLS称这类证明为“通透证明”（或者有时候也称“全息证明”）。尽管次线性时间证明校验在哲学层面相当有趣，验证者的时间其实也不是最有产出的约束方式。
Mario Szegedy Leonid Levin
结果，最激动人心的成果出自同时限制验证者使用的随机比特数目以及它所能访问的比特数。对于这样的验证者，我们可以给出定义如下。这个定义最初是在Arora-Safra '92中给出的，
Sanjeev Arora Muli Safra
但其重要性是在更早的文章Feige-Goldwasser-Lavász-Safra-Szegedy '91（FGLSS）中首次指明的：
Uri Feige Laci Lovász
定义 5 PCP
是具有这样的PCP体系的可证明语言类，该体系使用 
个随机比特，质询证明中的 
个比特，并具有完备性1，可靠性1/2。
有了此定义，可以看出BFL的MIP=NEXP结果等价于NEXP⊆PCP[poly,poly]【译注：这一结论并不显然。或许需要利用交叉质询的原理将MIP转换为PCP。】。同样，如果你以恰当的方式看待BFLS多对数时间验证者的结果，也可以将其看成是表明了NP⊆PCP[polylog,polylog]。后一结果显然被Feige, Goldwasser, Lavász以及Safra（在普林斯顿）独立地注意到了（就在其后不久），并予以证明。之后Szegedy加入了这一小组，然后他们发表了一个改进结果，连同一个深刻的应用。正是这一应用惊呆了所有人，并在此后数年里让PCP研究如火中天：
定理 6 （FGLSS, FOCS '91） NP ⊆ PCP
，其中 
. 此外，无法近似最大团到任何常数因子，除非NP ⊆ DTIME
. 【译注：DTIME(·)为具有给定确定性算法时间的复杂类。】
从这一结果看来，显然NP ⊆ PCP[
]应该会是对的；此外，现在有了大量的额外动机去证明它并对这些PCP结果加以改进，因为它们会对近似团的困难性有所推论。这一结果由Arora和Safra在伯克利于1992年早期（在Nisan的邮件之后两年多一点）在一篇文章中证明，其中引入了非常多的技术进展，并采用了缩写“PCP”以及先前提到的PCP记号。首字母PCP似乎出自Safra，并且很明显这两位伯克利作者知晓PCP同时也是一种致幻剂的名称。这一命名看起来似乎是由加利福尼亚某处的一次会议中的一场事故诱发的，当时警察进入Safra待的会议酒店房间，试图进行一次毒品（PCP?）搜查（结果不在Safra身上——他们走错了房间！）
定理 7 （AS '92）NP ⊆ PCP[]。事实上，NP ⊆ PCP[
]。
因此事实上，质询数可以是次对数的。其实，归功于Arora, Motwani, Safra, Sudan和Szegedy的一篇未发表（未写成？）的手稿指出基本上同样的证明可以将质询数降到
。
Rajeev Motwani Madhu Sudan
Muli接着前往以色列度暑假了，我觉得；此后不久迎来了最终改进结果的发表。
定理 8 （Arora-Lund-Motwani-Sudan-Szegedy '92） NP ⊆ PCP[
]。（尽管从未被明显计算出来，证明的质询数传言大约为
）
这一成果如今被称为“PCP定理”，并通常被同时归功于Arora-Safra '92与ALMSS '92。ALMSS的改进吸收了Lapidot-Shamir '91，Feige-Lovász '92，以及Blum-Luby-Rubinfeld '90中的想法。AS和ALMSS都出现在FOCS 1992上——它们与Nisan, Szemerédi, 以及Wigderson的一篇名为《
空间中的无向连通性》的文章共享一个会议时段。事实上，在FOCS之前六个月，4月7日，结果就已经由Gina Kolata写到《纽约时报》的科学版了（《长数学证明获得全新捷径》），并且在那一周后有公告称在STOC '92上将会有这些结果的一次非正式报告。（这一公告逐字抄录于下，以展现STOCs与FOCSes以前看起来是多么地好玩。STOC 讽刺剧？抽彩？海上皮划艇？本地传说，庆典，以及舞蹈？裸体蹦极？！）
Dror Lapidot Mike Luby Ronitt Rubinfled
PCP定理被视为复杂性理论的巅峰以及冠冕之宝，尽管后续还有大量对这一定理的各种改进。FGLSS '91, AS '92以及ALMSS '92因为各自贡献一同分享了2001年度的Gödel奖。
附录：STOC '92的公告。
The STOC '92 announcement.
Date: Mon, 20 Apr 1992 10:37:07 -0400
Reply-To: Michael Fellows
Sender: TheoryNet List
Subject: STOC '92 update
Update Information on STOC 92, Victoria, May 4-6:
(1) Yes, clothing is optional on the bungee jumping; no, we did not engineer the evening television news story which played across North America as a promotional event for STOC 92, it was just a coincidence.
(2) Discounts are available on Hertz rental cars, when arrangements are made through the United Airlines Convention desk.
(3) Victoria Taxi is the official taxi for STOC 92, and they are guaranteeing a rate of $32 (Can) between the Empress and the Victoria International Airport. Their phone number is 383-7111 in Victoria.
(4) Some phone numbers re: travel to Victoria Lake Union Air (Seattle - Victoria) 800-826-1890 Victoria Clipper (Seattle - Victoria) 604-384-8322 BC Ferries 604-656-0757 Helijet Airways (Vancouver - Victoria) 604-382-6222 Black Ball Ferries (Port Angeles - Victoria) 604-386-2202 Washington State Ferries (Seattle or Anacortes to Victoria) 604-381-1551
(5) Another route to Victoria is via the Anacortes ferry. Anacortes is about one hour's drive north of Seattle; this is a very pretty trip of about 3 hours through the San Juan islands. The ferry from Anacortes runs less frequently, so be sure to check the times with the number above if you choose this route.
(6) Oops! This will not be the first ever STOC follies; there have been two previously, one in 1978, and the last in San Francisco in 1982. If you wish to communicate or coordinate concerning the follies, contact Maria Klawe.
(7) There will be a raffle on Tuesday night, with raffle tickets awarded for submission of a topic in theoretical computer science together with a way that the topic might be presented in problem-solving mode to schoolchildren. For more details about this raffle and the project of assembling a compendium of theoretical computer science topics and presentation strategies for schoolchildren, stay tuned to theorynet.
(8) Sea-kayaking has filled up for Sunday! We are offering also a hike along Finlayson Arm from 10:30 AM until mid afternoon. Let us know if you are interested.
(9) The venue of the banquet on Tuesday night has been changed to the Native Heritage Center of the Cowichan Band, located in Duncan beside the Cowichan River. This is a feast, introduced and presented with native traditional story, ritual and dancing. The Center has several galleries and other displays of native arts, crafts and history. Bus transportation from the Empress will be provided. ONE PAGE ABSTRACTS OF RECENT RESULTS FOR DISTRIBUTION AT THE MEETING ARE ENCOURAGED AND WILL BE ACCEPTED UNTIL APRIL 28 The purpose of this is to encourage informal communication of the most recent results in the field. We are modeling our effort on the similar service offered by the Structures in Complexity meeting.
(10) A number of exciting developments are now scheduled for informal presentation, including the results from Berkeley which were written up in the New York Times last week.
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。
链接地址：https://wap.sciencenet.cn/blog-863936-1492416.html?mobile=1
收藏
