编译 | 张林峰（普林斯顿大学应用数学专业博士研究生）

责编 | 陈晓雪

 

●　●　●

 

P和NP是否相等通常被认为是理论计算机科学中最重要的难题，也是克雷数学研究所高额悬赏的七个千禧年难题之一。

 

5天前，德国波恩大学的计算机科学家Nobert Blum在arXiv上传了一份38页长的论文，声称证明了P/=NP（P不等于NP），引发学界的关注与讨论 (https://arxiv.org/abs/1708.03486)。

 

很快，加州大学伯克利分校的电子工程与计算机科学教授Luca Trevisan就在社交平台上发表意见称，安德烈耶夫方程 (Andreev’s function)，也即论文证明中的关键，在文中被认为具有超多项式电路复杂度 (superpolynomial circuit complexity)，而实际上可以被高斯消去法 (Gaussian elimination) 解决，所以仅有多项式复杂度，这使得文中的证明不能成立。该证明是否正确还有待人们的进一步仔细检查。

►Luca Trevisan认为，Blum文中的证明不能成立

 

近年来，不乏有人声称证明了P等于或者不等于NP，但都被发现证明过程有误。事实上，到目前为止，还没有人能够回答这个问题。2002年，有70位数学家和计算机科学家被邀请参与一次投票，投P是否等于NP。其中的61位认为P不等于NP，而剩下的人里有好几个都表示投“等于”只是为了采取相反的立场。

 

粗略地说，P代表一组相对容易的问题，而NP代表一组看起来非常难的问题。因此，P= NP将意味着明显困难的问题其实有比较容易的解决方案——当然，其中的细节还要麻烦一些。

 

实际上，量子计算机、图同构问题等人们热衷的最新进展无不指向P对NP问题。那么，P与NP问题究竟是什么？它的解决将意味着什么？它难在哪里？量子力学为它带来了什么？又有什么理论、将在何时有可能解决它？本文试图对这些问题提供简单的介绍和探讨。

 

1 当我们说P/NP问题时，说的是什么？

 

图灵时期的计算机科学关注的主要是问题的可计算性（computability），也即一个问题是否可以被计算机描述并解决。之后，随着可计算性问题的澄清，计算机科学家逐渐将注意力转移到了另一个问题，即问题的复杂性（complexity）：执行一个给定的算法需要多长时间？不过，计算机科学家的答案不是几分钟或者几毫秒，而是所需时间与问题规模的函数关系。

 

《麻省理工学院新闻》(MIT News）曾发表过一篇解释P/NP的文章。这篇文章指出，想象有一张未经排序的数字列表，然后写一个寻找最大值的算法。首先显然，该算法必须要查询列表中的所有数字。但是，如果它只是在每一步查询一个数字，然后只更新并记录当下的最大数，那么对于每个数字，它只需要查询一次。于是，该算法的执行时间与它处理的问题规模，即计算机科学家们所指的N，直接成正比。当然，大多数算法是更为复杂的，因此比寻找最大值算法的效率要低。但是有许多常见算法的执行时间与N^2，或者N log(N)成正比。

 

 

一个只包含常数、N、N^2以及N的其他次方的数学表达式称为一个多项式（polynomial），这就是“P = NP”中的“P”所代表的单词。一般来说，P代表求解时间与N的多项式成正比的问题的集合。类似地，PSPACE代表所用空间与N的多项式成正比的问题的集合。

 

显然，一个执行时间与N^3成正比的算法的要比与N成正比的算法慢（对于足够大的N），但这种差异与多项式和指数的差异比起来要渺小得多。《麻省理工学院新闻》的这篇文章指出，如果一个执行时间与N成正比的算法用1秒可以解决包含100个输入元素的问题，那么与N^3成正比的算法大概需要3个小时。但是，一个执行时间与2^N成正比的算法需要300艾（1艾等于10的18次方）年的时间来解决同样的问题。所以2^N与N的多项式的差异要比N^3和N之间的差异多的多。

 

NP（Nondeterministic Polynomial time，非确定型多项式时间）指的是其解可以在多项式时间内被验证的问题集合。容易想象的是，许多NP问题看起来需要指数时间来解决。例如，对于大整数质因子分解这个或许是NP中最著名的问题，验证一个解几乎只需要做一次乘法，但要真去解的话似乎需要系统地尝试大量的可能解。

 

所以“P是否等于NP”的意思是说“如果一个问题的解可以在多项式时间内被验证，那么是否可以在多项式时间内找到这个解”。这个问题的部分魅力在于，大量典型的看起来需要指数时间去解决的NP问题被称为“NP完全问题”（NP-complete，NPC），它们可以在多项式时间内相互转化。这意味着如果其中一个问题是多项式时间可解的，那么所有其他问题也都是。第一个NPC问题是库克-列文 (Stephen Cook， Leonid Levin) 给出的布尔可满足性问题（Boolean Satisfiability problem，SAT）。于是，任何NP问题都可以在多项式时间内转化为SAT问题。与此等价地，如果SAT在P中，那么P=NP。这便是著名的库克-列文定理（Cook–Levin theorem）。

 

在现实生活中，NP完全问题是相当普遍的，特别是在大的调度任务中。《麻省理工学院新闻》曾列举了一个著名的NP完全问题是所谓的旅行商问题（Traveling Salesman Problem，TSP）。该问题在当今很发达的物流业中可以表述为：一个物流配送公司欲将N个客户的订货沿最短路线全部送到，那么它应该如何确定最短路线？对于这一问题，P=NP意味着这样的物流分配可以很快地进行，但反之则意味着当物流规模逐渐扩大时，我们将无法在有效时间内找到最短路线。

 

综上，我们将P、NP、NPC以及PSPACE等复杂度类及它们之间相互的关系总结如下图。我们还知道，SAT与TSP在NPC中，而图同构和大整数分解等问题既没有被证明在P中，也没能被证明在NPC中，大部分理论计算机科学家认为它们的难度介于P与NPC之间（NP-intermediate,NPI）。

 

2 P/NP问题有什么用，又难在哪里？

 

几乎没有一个数学家、物理学家或者计算机科学家相信P真的等于NP——那样的话，所有的密码将很容易被破解，很多困扰人们的数学问题将有办法被解决，人工智能将突破连连……一个想到答案和验证答案所需时间相当的世界，会是我们所生存的世界吗？如果是的话，为什么世界上最聪明的数学家会对着一些数学问题思索良久，而当他们想出答案时，又是那么快地就能验证答案是否正确呢？既然大多数人觉得P不等于NP，那么它的证明究竟有什么用？研究它又有什么意义？

 

麻省理工学院（MIT）数学系主任以及计算机科学、人工智能实验室计算理论小组（Theory of Computation Group，TOC）成员Michael Sipser认为，P/NP问题有助于我们更加深入地理解计算复杂性。“一个主要的应用是在密码学领域，其中密码安全性经常是由计算任务的复杂性保障的，”Sipser说，“互联网安全交易常用的RSA加密方案就是研究特定数论计算复杂性问题时的一个副产品”。此外，“P/NP问题已经被数学界的人们广泛认为是基本、重要而美丽的数学问题。我认为它是数学和计算机科学之间的桥梁。”

 

对于同样的问题，TOC的另一位成员、MIT计算机科学和人工智能实验室副教授Scott Aaronson（现为德克萨斯大学奥斯汀分校计算机科学教授）也提供了他的回答：“是的，几乎所有的人都相信P是不等于NP的。但是，研究这个问题的过程要比结果重要。这个过程中，为了证明它，我们将需要大量的对计算的崭新理解。我们想要证明的是什么？是对于解决所有这些优化问题、搜索问题、找到定理的证明、找到航空公司的最佳路线设计、破解密码——所有这些不同的东西，无论你多么聪明，都不能找到有效的算法。所以，为了证明这样的命题，一个先决条件就是要了解所有可能的有效算法组成的空间。这可是一个令人难以置信的艰巨任务。我们期望的是，在证明这件事情的过程中，我们会了解到大量的远超我们想象的关于有效算法的理论，而且非常非常有可能发现新的、当下无法预知的在某些地方有神奇应用的算法。理论计算机科学的历史经常是这样的，你用来证明一些东西不可能的论据恰恰可以反过来说明别的东西可能，反之亦然。最简单的例子是加密，当你证明一些问题难以被有效解决时，你也会得到一个有用的编码方法。”

 

值得一提的是，在研究P/NP问题时，很多复杂性类的引入有着广泛而深入的理论意义和实际意义，有界错误概率多项式时间类（bounded-error probabilistic polynomial time，BPP）便是其中之一。此时不得不提的便是概率算法。一方面，20世纪80年代以来很多科学家认为概率的引入有助于解决P/NP问题。另一方面，如果非要和下文中的量子力学扯上关系，概率算法是非说不可的——量子算法天然便是概率算法！

 

典型的概率算法包含“掷硬币”的指令，并且掷硬币的结果可能影响算法后面的执行和输出。BPP是这样的一类判定问题：如果答案是肯定的，那么存在⼀个多项式时间随机算法以⼤于2/3的概率接受，如果答案是否定的则⼩于1/3。换句话说：给定任何输⼊，该算法错误的概率最多为1/3。1/3这个数字的意义仅仅在于它是某个⼩于1/2的正的常数。任何这样的常数都是⼀样好的。为什么呢？嗯，假设我们得到⼀个犯错概率为1/3的BPP算法。如果我们真想要的话，我们可以很容易地将这个算法的犯错概率修改为最多（⽐如说2^{-100}）。怎么做呢？我们仅需要反复运⾏该算法⼏百次，然后输出占多数的答案！所以，这就是BPP：很多人认为，BPP是经典物理学控制的宇宙中计算机可以切实解决的所有问题组成的类。

 

BPP与P、NP等的关系如何呢？显然，P包含于BPP，因为P便是不需抛硬币、输出结果确定的BPP。而现在很多科学家认为，P可能等于BPP，这是又一个开放性问题。有趣的是，我们甚至还不知道BPP与NP的关系，而只知道BPP包含于PSPACE。因而，下面的关系图中，虚线又增多了：

 

看起来，BPP的加入未必可以解决P/NP问题，反倒带来了更多尚未有答案的问题。而事实上，更多的复杂度类因为研究的需要被引入了进来。在Scott Aaronson开的复杂度类动物园（Complexity Zoo）中，人们不断地加入新的复杂度类，到现在已经有了498只复杂性类！人们不知道这个研究过程何时是个终点。

 

综上所述，如果P=NP成立，那么世界将换一个模样；而如果能够证明二者不相等，我们也会取得足够多的新突破。这正是其重要性所在。而它很困难的原因恰恰在于，我们还没能较为清楚地看到一条通往它的道路。

 

3 量子力学带来了什么？

 

“你要是光看报、读杂志等，你可能会觉得一个量子计算机可以通过‘并行地尝试每一个可能的解’，然后‘在心脏跳一下的时间里解决NP完全问题’。嗯，大概那是门外汉们对于量子计算机最核心的错误印象。”Scott Aaronson在接受《麻省理工学院新闻》采访时说。

 

“Peter Shor（另一位TOC成员）发现大整数分解的多项式量子算法时，量子计算界确实炸了。”在《麻省理工学院新闻》的报道中，Sipser介绍说。“Peter的突破引发了计算机和物理两个领域的一大波研究。事实上，Shor的发现一度点燃了人们利用微观尺度下反直觉的量子力学来在多项式时间内解决NP完全问题的希望。但现在看来这似乎不太可能：大整数分解问题实际上是几个不知道是否为NP完全的NP困难(NP-hard)问题。”同样地，人们不能证明不存在多项式的大整数分解算法，所以尽管人们相信量子计算对于大整数分解这样的问题会带来计算能力的提升，但这点同样尚未得到证明——更别提对于一般问题的指数级别的突破了。

 

对此，Scott Aaronson介绍了Grover算法作为例子。Grover算法对于输入规模为N的无序数据库给出的~2^{N/2}时间复杂度的量子搜索算法。但早在Grover的算法之前，Bennett等人已经证明~2^{N/2}是最优解了！换句话说，任何在2^N那么大的大海中捞一根针的量子算法都需要至少~2^{N/2}步。相应地，经典计算机需要~2^N步。所以至少可以说，对于“一般的”或者“无结构的”搜索问题，量子计算机对于经典计算机来说只能给出某种加速——事实上是平方加速——但不会是像Shor算法那样的指数加速。

 

为什么这个加速会是平方的，而非立方或者其他什么的？Scott Aaronson尝试着给出了答案，且尽量不牵扯到Grover算法或者Bennett等人最优化证明的具体细节。他认为，从根本上讲，我们得到平方加速的原因是，量子力学是基于2-范数而非1-范数的。经典来讲，如果有N个解，其中只有一个是正确的，那么查询一次后我们距离得到正确答案便有了1/N的概率，查询两次后便有了2/N的概率，查询三次3/N，依此类推。因此，我们需要~N次查询来获得足够大（即接近1）的概率猜出正确答案。但是如果用量子力学，我们是对一组几率幅态矢进行线性变换，它是概率的平方根。所以我们这样考虑这个问题：查询一次后我们有1/\sqrt{N}的几率幅得到正确答案，查询两次后是2/\sqrt{N}几率幅，查询三次后是3/\sqrt{N}几率幅，依此类推。所以经过T次查询后，我们得到正确答案的几率幅为T/\sqrt{N}，然后概率便是|T/\sqrt{N}|^2= T^2/N。因此我们需要大约T ~\sqrt{N}次查询来得到接近于一的概率。

 

量子计算机概念的引入给我们带来了新的复杂度类，其中最典型的一个便是BQP，即有界错误量子多项式时间类（bounded-error quantum polynomial time）。与BPP类似地，BQP指可以在多项式时间内用量子计算机以小于1/3的错误概率解决的问题的集合。很多人认为，BQP是量子物理学控制的宇宙中计算机可以切实解决的所有问题组成的类。

 

BQP包含BPP与P，且包含于PSPACE，但它与NP的关系就没那么确定了。于是，新的关系图如下：

 

综上所述，量子力学的加入一定程度上为P/NP问题带来了新的曙光，但是想要解决P/NP问题还是需要走很长的路。

 

4 可能的解决方案？

 

在通往P/NP问题的路上，有很多的尝试，例如量子力学、电路下界、交互式证明技术等，都先是让人们看到了希望，然后随着研究的深入，又让人们觉得这些可能还不够。那么，还有什么“有希望的”解决方案吗？Scott Aaronson介绍了芝加哥大学计算机系教授Ketan Mulmuley的几何复杂性理论纲领（Geometric Complexity Theory program, GCT program）。GCT试图将P/NP问题与代数几何、表示理论等很多看起来比较远的数学概念联系起来。

 

“我觉得GCT就像计算机科学领域的弦论，”Scott Aaronson说，“一方面，它实现了如此惊人的数学联系，以至于一旦你看到它们，你就会觉得这个纲领一定会在正确的道路上。而另一方面，如果你用已经解决了多少它最初想解决的问题，而不是这一纲领本身来评价它的话，那么可能它连最初的想法都还没有实现。”也就是说，或许正是因为还没有足够深入的了解，所以GCT还保留着解决P/NP的希望。“甚至GCT纲领最疯狂的支持者也预测说得有几十年的跋涉，而且其在数学上的复杂性也吓唬到了其他每个人。”

 

是的，P/NP问题就是这么难。

 

感谢Scott Aaronson对本文的意见。

 

主要参考文献：

1. MIT News对于Michael Sipser和Scott Aaronson的采访，采访部分获Scott Aaronson授权翻译：

http://news.mit.edu/2009/explainer-pnp

http://news.mit.edu/2010/3q-pnp

2. Aaronson S. Quantum computing since Democritus[M]. Cambridge University Press, 2013.

3. Sipser M. Introduction to the Theory of Computation[M]. Cengage Learning, 2012.