计算机科学家如何学会重新发明证明

如果一百万计算机科学家一起吃晚饭，他们会支付巨额账单。如果他们中的一个人感觉特别节俭并想检查账单是否正确，那么这个过程会很简单，即使很乏味：他们必须仔细检查账单并将所有内容加起来，一次一行，以使确保总和等于规定的总数。

但在 1992 年，六位计算机科学家在两篇论文中证明了一条激进的捷径是可能的。总有一种方法可以重新格式化任何长度的账单，以便只需几个查询即可对其进行检查。更重要的是，他们发现任何计算，甚至任何数学证明都是如此，因为两者都有自己的收据，可以这么说：计算机或数学家必须采取的步骤的记录。

这种非常简洁的格式被称为概率可检查证明（PCP）。 （根据 Ryan O’Donnell的说法，该首字母缩略词显然是在警察错误地前往其中一位发明者 Shmuel Safra 的酒店房间时选择的，同时试图对苯环己基哌啶（也称为 PCP，或天使尘）进行可能的毒品调查。 .)

PCP 已成为理论计算机科学中一些最重要的工具。最近，它们甚至已经进入了实际应用，例如在加密货币中，它们用于将大批量交易汇总成更容易验证的较小形式。

斯坦福大学的Dan Boneh说：“我不知道有任何例子——或者可能只是非常罕见——这样深层次的代数工具实际上可以将其付诸实践。”

在创建 PCP 之前，计算机科学家已经通过类似于晚餐支票的解决方案确定了一整类问题——一旦获得，就很容易验证。但是对于其中许多问题，首先找到解决方案似乎花费了不切实际的时间。

计算机科学家将这类难以解决但有效验证的问题命名为 NP。它为我们关心的许多实际问题以及更抽象的问题（例如寻找数学定理的证明）提供了概念上的家。证明是循序渐进的方法，可以绝对确定地建立他们的数学结论——就像逐项账单提供欠款总额的证明一样。证明可能很难获得，但一旦你有了证明，就可以直接检查。这将证明完全归入 NP 的范畴。

在 1980 年代，计算机科学家开始重新构想证明可能是什么。密码学家想知道是否有可能在不查看证明内容的情况下知道证明是真实的。他们将证明的结构分成两部分系统，一个“验证者”试图检查一个由“证明者”提供的证明，后者以某种方式找到了证明。

1992 年的 PCP 定理表明，证明者总是有可能以新的形式对证明进行编码，这样无论证明的原始长度如何，都可以通过恒定数量的查询对其进行验证。必要的查询数量最终减少到只有两三个。验证者不会完全确定地知道这是真的，但是通过进行更多的查询，它可以稳定而直接地增加其确定性。结果违背了直觉。当然更长的证明需要你检查更多的证据？不是这样。

多伦多大学的Swastik Kopparty说：“这种事情是真的，真是不可思议。” “直到 PCP 定理被证明前不久，没有人敢发表这样的声明。”

该定理使人们对 NP 有了新的理解，并解释了它的一些有趣的性质。计算机科学家发现，对于一些 NP 问题，答案似乎不仅难以计算，而且也难以近似。 PCP 定理有助于解释原因。它说，如果找到了一个 NP 问题的解决方案，它总是可以重新格式化，使得来自验证者的大多数检查（比如 90%）都会通过（但不是全部，因为证明仍然只是概率性的）。因此，从验证者的角度来看，问题似乎已大致解决，准确率达到 90%。但是由于 NP 问题很难解决，通常很难为它们找到一个 PCP，因此也很难找到一个超过某个点（例如 90%）近似正确的解决方案。

科学家们还开始考虑 PCP 实际应用的可能性。不幸的是，90 年代的 PCP 效率极低。证明者需要数千年才能产生代表任何实际计算的 PCP。此外，任何实际的 PCP 都会很大，需要一个行星大小的硬盘驱动器。

但到 2008 年，研究人员发现 PCP 的大小和计算扩展速度要慢得多，这使得它们更易于管理。然后，在 2010 年代中期，研究人员开始构建更小的 PCP 新形式，称为交互式预言机证明 (IOP)，它增加了证明者和验证者之间的额外轮次交互，在每一轮中，证明者可以产生一些东西更小更快。

“通过添加交互并使用从 PCP 技术移植而来的大量相同数学，您可以获得实用的东西，”离开以色列海法 Technion 并创办 StarkWare 公司的计算机科学家Eli Ben-Sasson说。

在过去十年中，计算机科学家还在加密货币背后的软件中发现了 PCP（及其后代）的直接应用，这些软件现在也引发了他们自己的有趣的理论问题。在其中一个软件系统中，大型计算机（证明者）验证金融交易并将验证计算放入 PCP，以便较小的计算机（验证者）可以更快地验证交易。

但是假设证明者试图作弊，例如，通过在 PCP 中隐藏一组虚假交易。当一个 PCP 系统（由证明者、验证者和 PCP 组成）能够抵御这种欺骗时，研究人员称它具有“可靠性”。健全性在理论上和实际应用中都很重要，其中更好的健全性（由某个参数量化）转化为更快的验证和更少的计算工作。

Ben-Sasson、Dan Carmon、Yuval Ishai、Kopparty 和 Shubhangi Saraf 于 2020 年 5 月发表的一篇论文表明，现代 PCP 系统的可靠性达到了理论计算机科学的基本极限。这是数据以一种经典形式编码时已知的最大持久性，称为 Reed-Solomon 编码，这也是 PCP 对证明或计算进行编码的方式。

PCP 仍然可以提高效率。最近，两组研究人员发现了一种对大块数据进行编码的 最佳方法，这样只需检查几个点就可以发现整个块是否已损坏。此方法通过提供仅依赖于几个查询的完整性测试来执行类似于 PCP 的操作，同时在速度和大小方面也达到了完美的效率。研究人员将其视为一种概念证明，有朝一日可能会找到完美的最佳 PCP。

“这不是一个简单的问题，”德克萨斯大学奥斯汀分校的Dana Moshkovitz说。 “[但]感觉我们应该去做。”