不对称生成/验证成本 – 搞英语 → 看世界

我们倾向于认为生成解决方案和验证解决方案所需的工作量大致相等，假设您需要回溯生成步骤以验证它们是否正确。但有时验证可能比生成要容易得多[1]。

保理

例如，假设我生成两个 1000 位素数，将它们相乘，并要求您通过因式分解恢复这两个素数。验证是否找到解决方案需要一瞬间的时间，但找到解决方案实际上是不可能的。互联网的安全取决于这一事实。（请参阅此处有关RSA 加密的帖子。）

众所周知，生成式人工智能是不可靠的。但如果验证解决方案比生成解决方案容易得多，那么即使人工智能解决方案不可靠也没关系。我们最近有几个咨询项目，旨在评估法学硕士完成其应做的事情的情况。法学硕士并不完美——没有人预料到它们会如此——但任务是估计错误率是否可以接受。

乔治·波利亚 (George Pólya) 曾经说过：“为了解微分方程，你需要不断地观察它，直到找到解决方案。”他只是半开玩笑。微分方程课程提供的求解技术没有合理性[2]，但即使技术不能，解决方案也可以被证明是合理的：将解决方案放入方程中，看看它是否有效。

在过去 70 年里，已知最大的素数是梅森素数，但有一个例外 [3]。这是因为有一种方法可以比一般数更有效地测试梅森数是否为素数。

证明一个大数是素数需要大量的计算，但是可以产生一个可以快速验证的素数证书。素性证书的一种形式是普拉特证书，另一种是椭圆曲线素性证书。

某些优化问题（例如线性规划或更一般的凸优化）会生成验证解决方案是否最优的证书。也许解决方案是在强大的计算机上找到的，但可以在手机上验证。

证明解决方案存在通常比证明解决方案不存在更容易。您可以通过找到一个解决方案来证明存在解决方案。这可能不容易做到，但很容易验证。证明一个问题没有解决方案更困难——你怎么知道你是否已经足够努力了？——但有时你可以提供不可行的证明。

[1] 是否 P = NP 的问题询问在某种意义上是否可以有效地计算一大类问题的解决方案，而这些问题的解决方案可以被有效地验证 [4]。

[2] 求解技术是合理的，尽管达不到学生在学习微分方程入门课程时所具备的数学水平。

[3] 1989 年，已知最大素数为 391581 × 2 ²¹⁶¹⁹³ − 1。

[4] 脚注可以有脚注吗？当然，为什么不呢。 P=NP问题问的是一个可以在多项式时间内验证的问题是否可以在多项式时间内解决。但如果您还不知道这一点，您可能不会觉得这个描述令人满意。这有点微妙，我不会在脚注中添加脚注。