科学网—计算机科学家重塑证明之路
精选
已有 3611 次阅读
2024-12-7 10:33
| 个人分类: 编码 | 系统分类: 科研笔记
计算机科学家重塑证明之路
如果几条检验就够了，还有必要逐行去核实一个证明吗？
Mordechai Rorvig 著
左 芬 译
【 译注：原文2022年5月23日刊载于QuantaMagazine，链接见文末。 】
如果 一百万个计算机科学家共进晚餐，他们会累积一份巨长的账单。而如果他们中的一个特别节约，想要检验账单是否是对的，这个过程倒是直截了当，就是会有些冗长：他们得浏览整个账单，把所有条目一行一行地加起来，以确保总和与标出的总额一致。
可在1992年，六位计算机科学家在两篇文章中证明存在一条全新的捷径。总会有一种方式来重排账单——不论多长——使得仅用几次询问就可以完成检验。更重要的是，他们发现这对于任何计算，甚至任何数学证明都适用，因为二者也都带有它们自己的收据：也就是说，计算机或者数学家必须执行的步骤的记录。
这种极其简洁的格式被称为概率性可检验证明（Probabilistically Checkable Proof，简称PCP）（据Ryan O’Donnell说，警察曾误闯入发明者之一的酒店房间，试图进行一次针对苯环己哌啶的缉毒行动。而苯环己哌啶（phenylcyclohexyl piperidine）也被称为PCP，又叫天使尘。于是这一缩写就被拿来命名该证明了。）
PCP 已经成为理论计算机科学中最重要的工具之一了。最近，它们甚至进入了诸如数字货币等实用场景，用来将大批交易记录压缩成简短的形式，以便于验证。
“我从没见到——或者说极少能见到——如此深奥的代数工具进入实用场景的先例，”斯坦福大学的Dan Boneh说。
在PCP诞生之前，计算机科学家已经确认了求解起来跟晚餐账单类似的一大类问题——一旦找到答案，很容易验证。但对于许多这类问题，找到答案这一步看起来要花费不切实际的时间。
计算机科学家们把这类难以解决但易于验证的问题命名为NP。它从概念上囊括了许多我们关注的实际问题，以及更多的抽象问题，例如找到数学定理的证明。证明就是一步接一步的指令，从而以绝对确定性得出数学结论——就好比一份逐项的账单提供总额的证明。证明可能难以获得，但一旦你得到了，验证就是直截了当的。这说明把证明放在NP 类里是恰当的 。
“甚至直到PCP定理被证明之前不久，都没人敢于做出这一论断。”
—— Swastik Kopparty, 多伦多大学
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，所谓交互式谕示证明（Interactive Oracle Proof, IOP）。它在证明者与验证者之间增加了额外的交互轮次，在每一轮证明者会快速地生成非常简短的内容。
“通过引入交互性并使用从PCP技术中移植过来的大量数学，你可以得到实用工具。”Eli Ben-Sasson说道。他曾是位于以色列海法市的以色列理工学院的一名计算机科学家，离开后创办了StarkWare公司。
过去十年里，计算机科学家们还在数字货币背后的软件中为PCP（及其后裔）找到了直接应用，而这些数字货币如今又引发了许多独有的有趣理论问题。在这些软件体系之一中，一台大型计算机（证明者）会对金融交易进行核准，并把核准计算过程写成PCP，这样一台小型计算机（验证者）就可以更快地核准这些交易。
假定证明者想要欺诈，比如说，把一套错误交易隐匿在PCP里。当一种PCP系统（包含证明者，验证者，以及PCP）能防御这种欺诈时，研究者就称它具有“可靠性”。可靠性不仅在理论上很重要，在实用中也同样如此，因为更好的可靠性（以某个参数来量化）代表着更快的验证速度和更少的计算量。
Ben-Sasson ，Dan Carmon，Yuval Ishai，Kopparty以及Shubhangi Saraf于2020年五月发布的一篇文章表明，一种现代PCP系统的可靠性可以达到理论计算机科学的基本极限。这是数据在以所谓Reed-Solomon码这种古典形式进行编码时所能达到的最大已知耐用性，而证明或计算在编码成PCP时也采用了这种方式。
PCP 还能更加高效。最近，两个小组的研究者发现了一种最优编码方法，可以在编码一长组数据时只需检验几个地方就可以揭示出整个组是否已被损坏。这一方法完成的任务与PCP相似，在少量询问下提供对整体的检测，同时在速度和规模上都达到最佳效率【 译注：即c 3 猜想中的具有常码率与常码距比的局域可检测编码（locally detectable code）。 】。研究者们将其视为最优PCP将来也能找到的一种概念性证明。
“这并不容易，”德州大学奥斯汀分校的Dana Moshkovitz称，“【但】无论如何我们都应该放手一搏。”
原文链接：
https://www.quantamagazine.org/how-computer-scientists-learned-to-reinvent-the-proof-20220523/
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。 链接地址： https://blog.sciencenet.cn/blog-863936-1463299.html
上一篇： 计算机科学里程碑式的证明波及物理与数学 下一篇： MIP*=RE面面观