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

大数据文摘授权转载自zzllrr小乐

作者：Mordechai Rorvig

译者：zzllrr小乐

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

但在 1992 年，六位计算机科学家在两篇论文（https://ieeexplore.ieee.org/document/267823）中，证明了一条激进的捷径是可能的。对任何长度的账单，总有一种方法可以重新格式化，使得对其检查只需少量查询。更重要的是，他们发现任何计算，甚至任何数学证明都是如此，因为两者都有自己的“收据”，即：计算机或数学家必须采取的步骤的记录。

这种非常简洁的格式被称为PCP（概率可检查证明Probabilistically Checkable Proof）。（根据 Ryan O'Donnell的说法https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf，该首字母缩略词显然是在警察错误地前往其中一位发明者 Shmuel Safra 的酒店房间突击搜捕毒品后选择的，当时警察试图搜查毒品苯环己基哌啶（PhenylcyClohexyl Piperidine，也称为 PCP，或天使尘）。

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

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

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

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

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

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

多伦多大学的Swastik Kopparty说：“难以置信的是，这样的事情是正确的。” “直到 PCP 定理被证明前不久，没有人敢做出这样的声明。”

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

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

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

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

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

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

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

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

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

点「在看」的人都变好看了哦！