上篇文章已经提到，P vs NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中，NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。

历史上的进展

从上个世界70年代初这个问题被Cook提出以来，人们发展了各种工具来试图解决它，下面引自堵丁柱&葛可一的《计算复杂性导论》前言：

人们在七十年代开始对NP-完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破：基于NP问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。

到了八十年代中，对NP-完全问题的研究有了纵向的突破，在许多表面看来并不相关的计算模型之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题，同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工具，并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对NP类的刻划。由此得出了许多组合优化问题近似解的NP-完全性，从而刺激了算法界对近似算法研究的新热潮。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代数与编码理论等数学证明技巧。

但是，明显的，目前还没有一个看上去有希望的方向。相反的，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P vs NP问题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。

数学里最伟大的定理之一——费马大定理，用了数学家300多年时光。P vs NP问题，作为理论计算机领域最困难的问题，40年时间似乎太短了。

不过我还是相信，这个问题被拖这么长时间，是因为没有足够伟大的数学家来做这个问题。

大牛们怎么看？

对于NP是否等于P，大家看法不一。在2002年对于100个研究者的调查中，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。同时，在被询问到这个问题可能在何时被解决时，79个人给出了确切的数字，统计结果如下：

1. P=NP will be resolved between 2002-2009: 5
2. P=NP will be resolved between 2010-2019: 12
3. P=NP will be resolved between 2020-2029: 13
4. P=NP will be resolved between 2030-2039: 10
5. P=NP will be resolved between 2040-2049: 5
6. P=NP will be resolved between 2050-2059: 12
7. P=NP will be resolved between 2060-2069: 4
8. P=NP will be resolved between 2070-2079: 0
9. P=NP will be resolved between 2080-2089: 1
10. P=NP will be resolved between 2090-2099: 0
11. P=NP will be resolved between 2100-2110: 7
12. P=NP will be resolved between 2100-2199: 0
13. P=NP will be resolved between 2200-3000: 5
14. P=NP will never be resolved : 5.

在这份调查报告中，还有国际上著名的计算机学家对这个问题的看法，比如：

Avi Wigderson: (Institute of Advanced Study) I think this project is a bit premature. I think we know too little of what is relevant to even guess answers to your questions, certainly if "we" s replaced by "I"

The only thing I can definitely say, is that it is one of the most important and interesting questions ever asked by humans, and more people and resources should participate in filling up the holes that would allow better guesses of answers to your questions.

姚期智: (Princeton) It's hard to say when the question will be resolved. I don't have even an educated guess. Probably the resolution is that P is not equal to NP. I think the mathematical techniques used will be beautiful.

可能的极为诡异的结果

从实际应用来说，人们都希望NP=P，因为这意味着很多问题都能有有效的算法，但有些极为诡异的结果也是可能的，人们从这个结果中什么都得不到。

比如某一天人们最终使用某种数学上的技巧证明了NP问题的多项式时间算法的存在性，但并不知道如何找到它——这在数学上是极为可能的，那最终会怎么样呢？

这种情况不会发生，事实上，在NP=P的假设下，人们已经找到了NP完全问题的多项法解法，但这并没有好太多，因为这个算法是这样的： 此段有问题，还没想太明白。

// 接受NP完全语言的一个算法。
//
// 这是一个多项式时间算法当且仅当P=NP。
//
// “多项式时间”表示它在多项式时间内返回“是”，若
// 结果是“是”，否则永远运行。
//
// 输入：S = 一个自然数的有限集
// 输出：是 如果某个S的子集加起来等于0。
// 否则，它永远运行没有输出。
// 注：上面这是一个NP完全问题
//
// 程序数P 是你将一个整数P写为二进制，然后
// 将位串考虑为一个程序。
// 每个可能的程序都可以这样产生，
// 虽然多数什么也不做因为有语法错误。

FOR N = 1...infinity
FOR P = 1...N
以S为输入运行程序数P N步
IF 程序输出一个完整的数学证明（错误处在此）
AND 证明的每一步合法
AND 结论是S确实有（或者没有）一个和为0的子集
THEN
OUTPUT 是（或者不是）并停机

如果NP=P，上面这个算法便是一个NP完全问题的多项式时间算法。可是它一点价值都没有，更不用说来解决实际问题了。

另一种可能性：独立问题？

自从Godel的开创性结果以来，我们知道某些问题，比如连续统假设，是不可能从目前的条件（公理系统）推导出来的。有人怀疑P vs NP问题也是这样。这样的话，如果不存在NP完全问题的有效算法，我们不可能证明这一点。同样，如果存在一个有效的算法，我们也不可能找到它。

花絮

中国民科一向喜欢做大问题，不知为何很少向P vs NP问题下手，但他们的外国同行可不会客气，这里就有一大帮，而且这些国外的前辈们专业多了，好多解答还提供pdf文档下载呢。

参考文献：

1. P verse NP problem
2. The history and status of P verse NP question
3. 千禧年大奖难题（一）
4. 堵丁柱, 葛可一, 计算复杂性导论 , 高等教育出版社, 2002