在今年年初时，几位计算机科学家在arXiv上提交了一篇题为“MIP* = RE”的论文，这份长165页的论文旨在证明一个问题，即MIP*与RE是相同的。而这个精简的结论所代表的是复杂性理论中的一项里程碑式的发现，它解决了计算机科学、物理学和数学中的一系列待决问题。

什么是复杂性理论？什么又是MIP*和RE？故事可以从停机问题说起。简单地说，停机问题探讨的是，是否能以算法的方法判断一个计算机程序会终止运行还是无限循环运行下去。1936年，计算机之父阿兰·图灵（Alan Turing）提出了第一个关于计算机的一般理论，他证明了计算机不是全能的，有些问题本身是不可能用计算机得出结果的，停机问题就是其中一个例子。

这种思想革新了计算机研究领域。很快人们就意识到，就算有些问题的确能用计算机解决，但它所需的计算时间，可能直到地球被太阳吞没那天都无法完成。因此，仅讨论能否从算法上解决一个问题是不够的，根据求解的效率对解决方案进行分类才至关重要。

而复杂性理论就是根据解决问题的难易程度而对问题进行分类的计算问题的集合，一个问题的难易程度是根据计算这个问题所需持续的时间来衡量的。基于这种衡量标准，它将问题分成不同的类型，MIP*和RE所代表的便是其中的两类。

我们先来看RE类问题。

RE代表的是可以被计算机解决的那类问题，它还可以细分为一些子类。首先是P类问题，它代表的是可以用已知算法在多项式时间内解决的问题，或简单地说就是可以由已知算法快速求解的问题。例如两个数的相乘，再比如将数列从小到大排序，都属于P类问题，因为存在已知算法可以有效地解决这些问题。

另一个要说的复杂类问题是NP类问题。NP中的N表示“非确定性”，NP对应的是对于一些“是否”问题，当答案为“是”时，存在一个有效证明来表明“答案为是”。换句话说，NP类所包含的是一些可能很难求解，但却很容易检查其答案的问题。我们可以以“是否有办法走出一个迷宫”的是否问题为例：如果答案是肯定的，那么只要给出一个明确的路线，而我们顺着这个路线走找到了迷宫的出口，就能确信这个问题的答案的确为“是”；然而如果答案是否定的，那就是我们就得走遍整个迷宫，确定真的没有出路，才能确信问题的答案为“否”。

一个与P类和NP类有关的重要问题便是，P类问题与NP类问题是否相同，即能够被容易解决的问题集合是否也属于能够被容易验证的问题集合中？没有人知道这个问题答案，虽然大多数数学家认为P与NP是不同的，但至今无人能证明这一点。

到目前为止，我们只讨论到了普通计算机所面临的问题。但是，现代计算机正在发生根本性的转变，比如世界各地的科学家正在努力研发创造出更加强大的量子计算机。那么问题是，当新型计算机出现，并声称它们能解决普通计算机所无法解决的问题，我们要如何判断它是否正确呢？

让我们以警察审讯一名嫌疑人的审讯过程为例。在审讯过程中，嫌疑人需要撇清嫌疑以证明自己清白，警察必须判断嫌疑人所说的是否是真的，还是在撒谎。这两方之间存在一种”认知“层面上的不平衡，警察处于劣势。对应于复杂性理论中，嫌疑人对应于一台计算功能强大，会提出问题的解决方案的计算机，即所谓的证明者；而警察则是一台计算能力有限但试图解决问题的计算机，它需要向证明者提问，以确定答案是否正确，即所谓的验证者。二者构成了一个交互式证明系统，验证者用它来确定是否应该相信证明者。

继续以警察和嫌疑人的类比来说，就是这些问题是警察无法求解的，但如果嫌疑人是无辜的，那他们至少可以说服警察自己是无辜的。这样的问题属于IP类问题。

如果可以审问多个证明者，且证明者不能互相交流彼此的“答案”（就像警察审讯多个嫌疑犯时会避免他们串供的情况一样），那么我们就进入了MIP类问题。这种问题通过对证明者的回答进行交叉检查，为验证者提供了更多的信息，因此MIP类问题包含了IP问题。

然而新的问题又来了。量子通信是一种新的通过量子位进行的通信形式。量子纠缠特性使得量子通信与普通通信之间存在根本上的差异。在量子通信的前提下，MIP类问题中的证明者可以共享一个纠缠的量子位，使得他们可以相互”交流“彼此的”答案“，由此导致MIP*类问题的产生。

如此看来，证明者之间的交流似乎显然只能有助于证明者协调谎言，而对验证者发现真相无益。因此，这种交流应该不能使计算问题变得更加可靠和更加可解。然而，新的证明却表示MIP* = RE，这一等式的成立它意味着，对纠缠的证明者进行审讯，是可以验证无法解决的问题的答案的。

这一证明的出现引发了一系列意想不到的结果。比如在20世纪70年代，数学家Alain Connes提出了所谓的科纳嵌入猜想，这是纯数学领域的一个重要问题，粗略地说，它探讨的是无穷矩阵能否用有限矩阵近似。这个猜想已经存在了40多年之久，大多数人都希望希望这个猜想是正确的，即无穷矩阵可以用有限矩阵近似，因为如果是这样的话，就可以证明其他的许多数学工具也是正确的。但是新论文的出现表明，这是不可能的，这种猜想是错误的。

再比如在1993年，数学家Boris Tsirelson指出了量子物理学中的一个问题，表明有两种不同的用于描述量子力学中的某个情况的数学形式，实际上是等价的。一直以来，物理学家利用Tsirelson的这个理论成功地解释了亚原子世界。然而MIP* = RE的结果表明，事实并非如此。这令物理学家们非常费解，他们困惑于如果是这样的话，为何这两种数学形式能产生相同的结果，也好奇于它们为何能描述相同的物理现实。

计算机科学中一个的证明，竟然对不同领域的重大问题的结果产生了如此深远的影响，真着实令人震惊。现在，量子物理学家和数学家仍在消化这些结果。相信由这个证明带来的惊喜与不解，时间会最终给我们答案。但毫无疑问的是，MIP* = RE是复杂性问题研究的一个巨大飞跃。

参考来源：

封面图来源：qimono / Pixabay

声明：转载此文是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与本网联系，我们将及时更正、删除，谢谢。