困难的问题实际上很简单？| 数学万花筒

   关注遇见数学, 遇见更精彩的自己

» 跳转观看视频《P与NP复杂度问题》

下文节选自《数学万花筒 I》, 已获人邮图灵授权许可, [遇见数学] 特此表示感谢! 

数学万花筒（修订版）

作者：［英］伊恩·斯图尔特

当当 广告

购买

困难的问题实际上很简单？

或者如何通过证明显而易见的事情赢得百万美元奖金？自然，事情不会那么显而易见，毕竟正如科幻小说作家罗伯特·海因莱因所说，TANSTAAFL（世上没有免费午餐）。但人总要有点梦想嘛。

我在这里指的是七个千年奖问题（参见第123页）中的一个，解决这个问题的人将会赢得百万美元奖金。它的技术性名称是P=NP?问题。名字听上去有点傻，但它所讨论的话题意义重大：计算机计算效率的固有极限。

  跳转查看视频：

《什么是庞加莱猜想？》

  跳转查看视频：

《什么是黎曼猜想？》

计算机通过运行（由一系列指令构成的）程序解决问题。一个总在得出正确解答（假设计算机始终按设计者的要求行事）后中止的程序称为算法（algorithm）。这个英文词源自生活在公元800年前后的波斯数学家阿布·阿卜杜拉·穆罕默德·伊本·穆萨·花拉子米（al-Khwārizmī）。他还给我们留下了另一个英文词algebra（代数），后者源自他的《通过还原和平衡进行计算》（Hisab al-jabr w’al-muqabala）一书。

花拉子米，被誉为“代数之父”

算法可以用来解决特定一类问题，但如果它不能在合理的时间内给出结果，那它在实践中也是毫无用处的。这里的理论问题不在于计算机的运行速度有多快，而在于算法的实现需要多少步计算。不过，对于特定一类问题（比如找到依次访问若干个城市的最短路线），计算的步数还要取决于问题的复杂程度。如果有更多城市要访问，计算机也需要进行更多计算。

因此，度量一个算法的效率的一个好办法是，看这个算法解决一个给定复杂程度的问题需要多少步计算。一个自然的区分是，如果所需的计算是输入数据的某个固定次幂，则这样的计算是“简单”的；若所需  的计算增长得快得多，往往呈指数次，则这样的计算是“困难”的。比如，两个 n 位数相乘，使用传统的长乘法，大约可以在 n² 步内完成，所以这种计算是“容易”的。另一方面，求一个n位数的质因子，如果你逐个尝试小于n的平方根的每个可能的除数（这是最显而易见的方法），则大约需要3^n步，所以这种计算是“困难”的。我们称相应的算法分别能在多项式时间（P类）和非多项式时间（非P类）内完成。

找出给定一个算法能多快完成是相对简单的。更难的是，判断是否还有其他算法可能更快。最难的则是，证明你所找到的是所有有效算法中最快的，而对此我们基本上无能为力。因此，我们原本认为很困难的问题有可能事实证明其实很容易，只要我们能够找到更好的解决办法。而这正是可以赢得百万美元的地方——只要有人能证明某个具体问题不可避免总是困难的（也就是说，不存在解决这个问题的、可在多项式时间内完成的算法），或者另一种可能性，世上没有困难问题（尽管从现实的世道看来，这似乎不太可能）。

不过在你开始着手试图赢取百万奖金之前，有几件事你需要注意。首先，有一类“平凡”的问题是困难的，只是因为它的结果非常庞大。

“列出前n个自然数的所有可能排列”就是一个很好的例子。无论解决这  个问题的算法有多快，它都至少要花n!步才能输出结果。所以这类问题需要单独考虑，它们也被称为可在非确定性多项式时间（NP）内完成的问题。（注意到NP不同于非P。）对于这些问题，你可以在多项式时间内（也就是说，很容易地）验算一个可能的答案。

NP问题的另一个我常说的例子是拼图。它有时可能很难求解，但如果有人给你看一幅声称已经完成的拼图，你立马就可以看出他有没有拼对。一个更数学的例子是，找出一个数的因子：除一下，验算它是否能除尽，要比一开始找到那个因子容易得多。

P=NP?问题问的是，是否每个NP问题都属于P类。也就是说，如果你能很容易地验算一个可能的答案，那你也能很容易地找到这个可能的答案吗？经验告诉我们，回答很可能是“不能”——找到答案总是事情最难的部分。但还没有人能证明这一点，也无法完全确定事实就是如此。所以要是你能证明P不同于NP，或者相反地，两者相等，百万大奖你是受之无愧的。

最后还有一点，事实证明，所有可能表明P≠NP的问题在某种意义上都是等价的，因为任何NP问题可以在多项式时间内转化为任何特定NP完全问题的一个特例。不严格地说，NP完全问题是NP类中“最难”的问题， 它们最可能不属于P类。几乎所有可能表明P≠NP的问题现在已知都是NP 完全的。而由此得到的一个闹心结论是，在证明P≠NP上，没有哪个具体问题比其他问题更合适——它们要么一荣俱荣，要么一损俱损。简言之： 我们知道为什么P=NP?问题必定是个非常困难的问题，但这一点对于我们解决它毫无帮助。

我想，想必还有其他简单得多的赚取一百万的门路吧。(完）