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

如果有一百万名计算机科学家共进晚餐，他们会拿到一张巨额账单。如果其中一人特别节俭并且想检查一下账单是否正确，核查过程很简单但会很乏味：他们必须检查账单，一行又一行将所有的单项价格加起来，确保总数等于账单总额。但在 1992 年，六位计算机科学家在两篇 论文中证明可以采用一条激进的捷径。总有一种方法可重新格式化任意长度的账单，只用几个查询可以对其进行检查。更重要的是，他们发现任何计算，甚至是任何数学证明都是如此，因为两者都有自己的收据：计算机或者数学家都必须采取的步骤记录。

这种非常简洁的格式被称为概率可检查证明（PCP）。PCP 已成为理论计算机科学中最重要的工具之一。它们最近甚至进入了实际应用，例如在加密货币中被用于将大批量交易汇总成更容易验证的较小形式。在创建 PCP 之前，计算机科学家已通过类似于晚餐账单检查的解确定了一整类问题——只要你有一个解，就很容易验证。但是对于其中许多问题，先找到一个解要花费的时间似乎长得不切实际。

计算机科学家将这类难以解决但能高效验证的问题命名为 NP。它为许多我们关心的实际问题以及更抽象的问题（例如寻找数学定理的证明）提供了一个概念性的家园。求解是一步一步地求证，建立起绝对确定的数学结论——就像逐项汇总账单证明总额一样。求解可能会很难，但是一旦你有了一个解，就可以直接进行检查。这类证明就完全属于 NP 的范畴。