这篇长达165页的论文，用一个里程碑式的证明同时解决了量子物理学和理论数学的难题

正文

请到「今天看啥」查看全文

这个证明的作者们原本是想确定一种用于验证计算问题的答案的方法局限性，这种方法涉及纠缠。找到那个局限性之后，顺带解决了另外两个问题： 物理学中的 Tsirelson 问题（关于如何用数学建模纠缠）以及纯数学领域的一个相关问题（科纳嵌入猜想）。

最终，这些结果像多米诺骨牌一样级联到了一起。

「这些思想都是同一时间出现的。它们能以如此戏剧性的方式再次聚首，真是很不错。」该证明的作者之一多伦多大学的 Henry Yuen 说。此外，该证明的作者还有悉尼科技大学的季铮锋（Zhengfeng Ji）、加州理工学院的 Anand Natarajan 和 Thomas Vidick 以及德克萨斯州大学奥斯汀分校的 John Wright。这五位研究者都是计算机科学家。

不可定的问题

在计算机诞生之前，图灵就已经为计算方面的思考定义了一个基本框架。几乎在同时，他也表明始终存在某些计算机无法解决的特定问题。这就是常说的「图灵停机问题」。

经典设计中，计算机程序可以接收输入并产生输出。但有时候，程序会进入无限的循环之中，不停地重复工作。如果你遇到了这种情况，那只能手动终止这个程序。

图灵证明了，并不存在一个通用算法，可以确定一个计算机程序将停止还是永远运行。答案必须在运行这个程序后才能知道。

计算机科学家 Henry Yuen、Thomas Vidick、Zhengfeng Ji、Anand Natarajan 和 John Wright 合作证明了一个验证计算问题的答案的问题，却最终为数学和量子物理学领域的重大问题提供了解答。

「如果你已经等待了 100 万年而一个程序还未停止，你需要等待 200 万年吗？没办法知道答案。」滑铁卢大学数学家 William Slofstra 说。

用技术术语来说，图灵证明这个停止问题是不可定的（undecidable）——甚至可想象的最强大的计算机也无力解决。

图灵之后，计算机科学家开始根据难度来对其它问题进行分类。要解决更难的问题，所需的计算资源也更多，也就是说需要更多运行时间、更多内存。这些属于计算复杂性问题。

最终而言，每个问题的求解都涉及到两个重大问题：「这个问题的解决难度有多大？」和「验证答案正确的难度有多大？」

审问式验证

当问题相对简单时，判断答案正确与否也很简单。但问题变得更加复杂时，就很难直接判断了。但就算无法确认，你也能知道答案到底对不对。

此处就要提到「审问式验证」了。这个方法跟警察审问的逻辑差不多：

如果一个嫌犯讲的故事是精心编造的，那你可能没办法去验证每一处细节。但只需要针对这个故事提出一些问题，你就可以知道嫌犯是在说谎，还是在如实陈述。

套用到计算机科学术语上说，「审问」的双方分别是一台强大的计算机和一台更弱的计算机。其中强大的计算机（证明者）给出了一个解，较弱的计算机（验证者）则希望通过提问来确定该解是否正确。

举个简单的例子，假设你是一个色盲，另一个人（证明者）称两颗弹珠颜色不同。 你要怎么验证他说的是不是真的呢？

你可以把这两颗弹珠拿到身后混在一起，再拿出来让证明者区分它们。如果它们颜色真的不同，那么证明者应该每一次都能给出正确的答案。如果这两颗弹珠实际上颜色一样，那么证明者有一半的可能会猜错（就算超过半数的时间能说对，那也能肯定颜色不一样了）。

这种方法还可以验证大量不同类别问题的解。以此推之，当两个证明者针对同一个问题都给出解时，验证速度会变得更快。

就比如，你要审问的嫌犯如果有两个，解决一个犯罪案件就会更加轻松，因为你可以交叉检验他们的答案。如果这些嫌犯讲的是实话，那么他们所说的大多都对得上。如果他们在说谎，那么更多时候会出现互相矛盾的答案。

计算复杂性可能看起来完全是理论方面的问题，但其实也与真实世界联系很紧密。在求解和验证问题的过程中，计算机需要时间和内存资源，本质上这是物理问题。

请到「今天看啥」查看全文