译者注：
PCP（probabilistic checkable proofs）概率可检验证明定理是计算复杂性理论中的重要定理之一，
PCP 定理指出 NP = PCP [O(log n ), O(1)]
是近似计算难度理论的基石，它研究了为各种优化问题设计有效近似算法的内在困难。它被Ingo Wegener描述为“自库克定理以来复杂性理论中最重要的结果”。
本文用于辅助阅读最近译文《小乐数学科普：计算机科学家如何学会重新发明证明——译自Quanta Magazine量子杂志》。
来源：华盛顿大学官网CS课程 2005-9
https://www.cs.washington.edu/education/courses/
https://courses.cs.washington.edu/courses/cse533/
（zzllrr小乐 2022-5-24）
（这是作者 Ryan O'Donnell 推断的关于 PCP 定理历史的简要梳理。主要资料来源是 Babai 的文章 《电子邮件和意想不到的互动力量》（Email and the unexpected power of interaction）、Goldreich 的文章《证明系统的分类》（A taxonomy of proof systems），以及相应原始来源。可能有一些不准确和遗漏，对此我深表歉意并要求提前更正。由于此笔记是为华盛顿大学（UW）的课程准备的，因此还强调了与华盛顿大学 有关的一些细节。）
有了 Irit Dinur（2005 年 4 月）对 PCP 定理的激动人心的新证明，他的 PCP 定理课程不再需要涉及原始证明中的许多细节（如果有的话）。但是这个原始证明和导致它的七年工作形成了一段有趣的历史，当然值得一听。
PCP 定理的故事始于 1980 年代初在麻省理工学院，GMR（Goldwasser、Micali 和 Rackoff）的一篇论文将赢得有史以来第一个哥德尔奖：《交互式证明系统的知识复杂性》（The Knowledge Complexity of Interactive Proof Systems）。该文首次发表于 STOC '85。然而，据说它的草稿早在 82 年末就已经存在。事实上，据说它至少在 83 年的一篇论文中被引用过。故事还说，这篇论文被 FOCS '83、STOC '84 和 FOCS '84 拒绝，尽管尚不清楚这些拒绝的论文是什么形式的。
Goldwasser、Micali 和 Rackoff 实际上对证明所意味着的哲学概念很感兴趣，尽管他们论文的主要动机是密码学。该论文介绍了两个新概念：交互式证明和零知识证明。
定义 1
在交互式证明中，具有私人投币功能的随机多时间验证者与全能证明者进行交互；他们以多项式次数来回发送消息。正确的陈述应该有接受概率 1（“完整性completeness”）的证明，不正确的陈述应该被拒绝，不管证明如何，概率至少为 1/2（“可靠性”）。（实际上，GMR 最初允许 1 - 2⁻ ⁿ 完整性；事实证明这并不重要。）我们用 IP 表示具有交互式证明（interactive proofs）的语言类别。
这是 GMR 能考虑的最普遍的有效证明概念；他们以学生在课堂上与提供证明的讲师互动的想法为模型。至于他们关于零知识证明的其他概念，我们不会在这里详细介绍，只是要说，在传统证明中，除了它是正确的事实之外，你还可以“学习”关于该定理的许多东西，在交互式证明除了定理为真这一事实之外，你还可以得知“零附加信息”。GMR 的主要例子是“二次非剩余”问题。通过给出模的分解作为见证，在 NP 中不难证明一个数是二次非剩余（平方非剩余）；然而，这揭示了很多信息。GMR 对这一事实给出了“零知识”证明。这当然是零知识证明的一个有趣的例子，但不是交互式证明的一个有趣的例子，因为问题已经在 NP 中了。
独立于 GMR 并在同一个 STOC '85 上发表的是 Babai 的一篇论文，即随机性交易群论。这篇论文后来发表在期刊上，名为 《亚瑟王-魔法师梅林游戏：随机证明系统和复杂性等级的层次结构》（Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes），Moran 是合著者；事实上，这篇论文与 GMR 分享了有史以来的第一个哥德尔奖。Babai 曾与 Szemerédi 写过一篇论文，其中他基于一些未经证实的群论假设，证明了某些特定的群论问题在 NP 中（例如，对于由其生成元给出的有限域上的矩阵群，它的阶数至多为 k吗？）。Babai 想要得到一个无条件的结果，所以他独立引入了交互式证明的概念，尽管是公开的抛硬币，并证明他的问题有常数回合的交互式证明。特别地，他给出了以下定义：
定义 2
AM[k] 是具有 k 轮的交互式证明类，其中验证者首先发言并公开抛硬币。（AM 代表 Arthur-Merlin，亚瑟王Arthur 是验证者，魔法师梅林Merlin 是证明者。）
Babai还证明了：
定理 1 对于所有常数 k，AM[k] = AM[2]
如今AM[2] 类简称为 AM。通过这个定义，我们看到 AM[poly] 与 IP 非常相似；主要区别在于公共硬币与私人硬币。此后不久 Goldwasser 和 Sipser (STOC '86) 表明他们是同一类。因此，在这篇论文之后，出现了一个很好的健壮的类，称为 IP 定义的（IP defined），它似乎捕捉到了具有有效证明的自由语言概念。
事实上，这门课很快就成为复杂性理论家感兴趣的一门课，原因如下：GMR 的交互式证明是针对已经存在于 NP 中的东西。Babai 的证明是针对他怀疑在 NP 中但没有足够的群论来证明的东西。但是在 FOCS '86 中（实际上，这个结果在 Goldwasser-Sipser 之前就已经被知道了一些），Goldreich、Micali 和 Wigerson 表明图的非同构性（Graph Non-Isomorphism） 问题存在于 IP 中，这是人们曾考虑很长一段时间，并试图放入NP的一个问题。
定义 3
图的非同构性是图的同构性的补：给定 G₁ = (V₁, E₁) 和 G₂ = (V₂, E₂)，两个邻接格式的图。它们是同构的吗？即是否可以重命名顶点以使它们是相同的图？
定理 2 (GMW '86) 图的非同构性在 IP中
证明：
验证者随机选择 i ∈ {1, 2}，随机排列 Gi 的顶点，并将结果图呈现给证明者。证明者必须猜测 i。对于完整性来说，如果图是非同构的，那么全能的证明者当然可以识别 i。对于可靠性来说，如果图是同构的，那么无论 i 是什么，证明者都会在图上看到相同的概率分布；因此它所能做的就是猜测。
在此之后的一段时间内，IP 方面没有任何重大进展，尽管交互式证明继续受到加密社区的关注。特别是，在 STOC '88 中，为了从有关零知识证明的一些结果中删除密码学假设，BGKW（Michael Ben-Or、Goldwasser、Joe Kilian 和 Wigderson） 引入了多证明者的交互证明的概念：
定义 4 (BGKW '88.) MIP ：具有多个非通信证明者（Multiple, noncommunicating provers）的交互式证明（IP）类。
BGKW 的一个定理表明，具有多项式个证明者的 MIP 与具有两个证明者的 MIP 相同。
再有一段时间，由于交互式证明的复杂性，事情停滞不前。Babai 猜想 IP = AM，事实上大多数人似乎认为 IP（甚至 MIP）只是 NP 的略微随机的推广。从哲学的角度来看，这似乎是非常合理的：为什么人们应该期望从有效证明概念的这种合理推广中获得显著的额外力量？88 年的 Fortnow 和 Sipser 表明，有一个预言机相对于其 coNP 不在 IP 中；同年，Fortnow、Rompel 和 Sipser 将这一结果推广到 MIP。（这篇论文还使用证明检查对 MIP 进行了重新定义，这将在以后证明是有用的……）由于这个预言结果，任何类似 coNP ⊆ MIP 的证明都需要复杂性理论中的一种前所未见的证明技术（特别地，是一种非相对化技术）。正如Babai后来所写的那样，这是一个相当大的“情感障碍”。
因此，当 1989 年 11 月 27 日，Nisan 向一些同事发送了一封电子邮件，表明（Permanent and hence）P#P ⊇ PH （Toda早在 1989 年证明）是在 MIP中。然后Nisan到了南美度假。值得注意的是，他的论文建立在 1989 年 M. Blum 和 S. Kannan 的程序检查、Lipton 的Permanent的随机自还原性以及 Beaver 和 Feigenbaum 的预言和代数编码的最新工作的基础上。.
Nisan 的结果非常令人印象深刻，但有些人质疑 MIP 的相关性——虽然 IP 作为有效证明的概念听起来很合理，但 MIP 貌似并不清楚。仅仅两周后，情况发生了巨大变化。12 月 13 日，Fortnow 在芝加哥为三人小组（Karloff 和 Lund）写作，向几十名同事发送了一封包含 LATEX 的电子邮件，以证明 P#P（Permanent and hence）在 IP 中。这绝对是非常令人惊讶的，因为这意味着 IP 比人们意识到的要强大得多。不仅coNP在其中，整个多项式时间层级也在其中。关于 Fortnow 电子邮件收件人的旁注：华盛顿大学教授 Martin Tompa 参与其中，在我看来，威斯康星大学教授 Richard Ladner 也参与其中。正如 Babai 所写，值得注意的是，Razborov 或其他任何来自东欧的人都没有出现在名单上。请注意，柏林墙仅在一个月前（11 月 9 日）倒塌，而苏联还剩下一年半的时间。另一个旁注，关于这个结果的功劳：Lund 被列为论文的“第一作者”，违背了字母顺序的标准做法，因为他显然提出了证明中的关键步骤。Fortnow 后来写道，他认为这是一个错误的决定。此外，Nisan 被添加为本文的合著者。因此，这个结果的通常归功于：
定理 3 (LFKN '90) P#P ⊆ IP
现在早就知道 IP ⊆ PSPACE（这个结果通常归功于 P. Feldman '86，尽管我在他关于《违背自然的游戏》“Games Against Nature”的论文中也看到它归功于 Papadimitriou '83）；显然，在这封电子邮件之后，试图证明反包含的比赛开始进行。仅仅两周后就完成了：Shamir 于 1989 年 12 月 26 日发送了一封电子邮件，介绍了一些新的聪明技术来证明：
定理 4 (Shamir '90) IP = PSPACE
（请注意，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 年获得博士学位。华盛顿大学的论文因其对游戏和交互式证明的计算复杂性研究而获得 ACM 博士论文奖。Condon 的 91 年早期 STACS 论文中的一个结果特别令人感兴趣。在该文中，她表明 NP 正是一类具有交互式证明的语言，其中验证者具有对数空间和对证明的单向读取访问权限。（Condon 和 Ladner 后来对该结果进行了技术改进。）主要的证明工具来自 IP = PSPACE 结果。但此外，作为推论，该论文表明矩阵的 MAX-WORD 问题（给定向量 u、v、矩阵 M₁、⋯、Mt 和 k，最大化 < u, Mi₁⋯Mik v >）没有常数因子逼近算法，除非 NP = P。这是有史以来第一次在交互式证明和逼近难度之间建立联系。然而不幸的是，Condon的结果并没有得到太多的历史赞誉，因为空间受限的验证者被证明不是最有效的限制途径。为验证者考虑的另一个限制是限制他们的时间。BFLS（Babai、Fortnow、Levin 和 Szegedy) 在 1991 年初/中期的结果表明，如果证明者被限制使用某种纠错码来编写证明，那么验证者可以使用多对数时间检查所有 NP 语言。BFLS 将此类证明称为“透明证明”（或有时称为“全息证明”）。尽管亚线性时间证明检查的可能性在哲学上非常有趣，但验证者时间也被证明不是最有效的限制途径。
碰巧的是，最令人兴奋的结果来自同时限制验证者使用的随机比特数和进行证明比特访问的数量。对于此类验证者，让我们先定义 Arora-Safra '92，尽管该定义的重要性在较早的论文 Feige-Goldwasser-Lovász-Safra-Szegedy '91 (FGLSS) 中首次阐明：
定义 5
PCP[r(n), q(n)] 是可使用 PCP 系统证明的语言类别，该系统使用 O(r(n)) 位随机性，在证明中查询 O(q(n)) 位，并且具有完整性 1，可靠性 1/2。
有了这个定义，可以看出 BFL 的 MIP = NEXP 结果等价于 NEXP ⊆ PCP[poly, poly]。此外，如果你以正确的方式查看 多对数（polylog） 时间验证器上的 BFLS 结果，它可以被视为显示 NP ⊆ PCP[polylog, polylog]。Feige、Goldwasser、Lovász 和 Safra（在普林斯顿大学）显然独立地（稍晚一点）证明了后一个结果。后来 Szegedy 加入了这个团队，他们发布了一个改进的结果，以及一个让每个人都感到惊讶的引人注目的应用，并在接下来的几年里点燃了 PCP 研究：
定理 6 (FGLSS, FOCS '91) NP ⊆ PCP(f(n), f(n))，其中 f(n) = log n · log log n
此外，作为一个相当直接的结果，不可能将 MAX-CLIQUE 逼近在任何常数范围内的因子，除非 NP ⊆ DTIME (n^( log log n))。
从这个结果可以看出 NP ⊆ PCP[log n, log n] 必须为真；此外，现在有巨大的额外动力来证明它并改进这些 PCP 结果，因为它们对近似团的难度产生了影响。这一结果在 1992 年初（在 Nisan 的电子邮件之后两年多一点）被伯克利的 Arora 和 Safra 在一篇介绍了许多技术发展的论文中得到了证明，其中包括首字母缩略词“PCP”和 PCP[r(n), q(n)] 符号前面提到过。首字母 PCP 似乎是由于 Safra 而这些伯克利的作者肯定不会忘记 PCP 也是致幻剂的名称。这个名字显然是出于某种原因，在加利福尼亚某个地方的一次会议上发生了一起事件，警察来到了 Safra 住的会议酒店房间，想要突击搜查毒品（PCP？）（而不是针对 Safra ——他们走错了房间！） .
定理 7 (AS '92) NP ⊆ PCP[log n, log n]
事实上，NP ⊆ PCP[log n,(log n^{.5+ϵ}]。
所以事实上，查询可以是次对数的。事实上，一份归因于 Arora、Motwani、Safra、Sudan 和 Szegedy 的未发表（未成文？）手稿注意到，基本上相同的证明得到的查询是 O((log log n)² )。Muli然后去了以色列过夏天，我想；不久之后公布了最终的改进。
定理 8 (Arora-Lund-Motwani-Sudan-Szegedy '92) NP ⊆ PCP[log n, 1]
尽管从未明确计算过，但据传使用的证明查询数量约为 10⁶
这个结果现在被称为“PCP 定理”，传统上归功于 Arora-Safra '92 和 ALMSS '92。ALMSS 的改进融合了来自 Lapidot-Shamir '91、Feige-Lovász '92 和 Blum-Luby-Rubinfeld '90 的想法。AS 和 ALMSS 都出现在 1992 年的 FOCS 中——他们与 Nisan、Szemerédi 和 Wigderson 的一篇名为 O(log¹.⁵n) 空间中的无向连通性的论文分享了一次会议——尽管结果的消息在 1992 年春天广泛传播，在 FOCS 之前的六个月，也就是 4 月 7 日，结果由 Gina Kolata 在《纽约时报》的科学版块《长数学证明的新捷径》（“New Short Cut Found for Long Math Proofs”）撰写，并在一周后公布将在 STOC '92 上对结果进行非正式的介绍。（此公告在下面逐字复制，以表明 STOC 和 FOCS 显然曾经是多么有趣。STOC 愚蠢？莱佛士？海上皮划艇？本土故事、仪式和舞蹈？裸体蹦极？！）
尽管随后对各种性质的 PCP 定理进行了许多改进，但其结果被认为是复杂性理论的顶峰和皇冠上的明珠。FGLSS '91、AS '92 和 ALMSS '92 共同分享了 2001 年的哥德尔奖。
联系客服
