重新认识P和NP问题

作为科班出身的程序员，我在算法课上早早地就接触到了P和NP问题。当然，当时仅仅将其作为课程中到一个可考核的知识点，简单的了解了相关概念。说实话，在两次算法课的学习过程中，我都对这对概念只是混了个眼熟，原因是其解释无聊且和其他算法概念关联性很弱。但现在看来，显然不是那样庸俗简单，这两个名词其实融合着有关哲学的，古往今来智者和探索者的故事。

那么还是复习一下定义：

P问题代表该问题能够在多项式时间内得到解决，而NP问题表示该为题可以在非决定性多项式时间内解决

需要注意的是NP并非不能在多项式时间内解决(Non-Polynomial)，而是非决定性多项式时间才能解决(Non-deterministic Polynomial)，更简单的解释是，NP问题可以在多项式时间内验证一个解是否正确。

我们说，乘法计算就是P问题，问题规模变大，运算的复杂度也只是多项式形式增长。而数独问题，当数独的规模变大(数独矩阵变大)，得到解的复杂度是成指数级增长，而我们能够在多项式时间内验证你给我的一个解是不是数独的解，所以数独问题是NP问题。所以再进一步理解，P问题其实是时间复杂度可以表示为多项式时间，而不是指数时间，而NP问题则只能表示为指数时间。

如果想要证明NP=P的这个目标，显然就需要找到一个算法，能够让一个NP问题的时间复杂度降到多项式时间。除此之外，实际上N问题和NP问题很难说有一个明确的边界，不过有一类NP问题在NP问题中算得上是“最难”的，肯定不是P问题，这种问题被称之为NP-Complete（NP完全）。由于NP完全问题绝对不属于P问题，那么能够让NP完全问题的时间复杂度降低为多项式时间，则就可以证明NP=P。

回想一下算法课时所学的那些算法，他们的目标基本上都是想要降低时间复杂度，但是没有一款算法能够降低NP完全问题的时间复杂度。典型的旅行商问题就是一个NP完全，而我们学过的对其最优解的动态规划算法也只能将时间复杂度降为$O(2^n * n^2)$。如果哪一天，有人能够灵光一现，想到一个算法，能将旅行商问题的时间复杂度降到多项式时间，那么NP问题就等同于P问题了。

看上去证明NP=P也不是那么难是吧。但事实上证明NP=P本身就是一个NP问题，也就是问题的解决方案变成了这个问题本身。所以很多研究者因此认为NP不可能等于P(81%)，我们不能通过数学推导或者天才的想法来得到NP=P（至少在现在这个数学框架下不行）。

那么再回过头来，为什么我们要纠结于NP和P是否相等呢？或者说当NP=P时这个世界会发生什么变化？其实根据前面的定义来说，就是所有能够在多项式时间验证解的问题，都能在多项式时间内得到解。有了计算机的帮助，这就意味着现实世界很多问题都可以用计算机很快得到解决，我们不用去关心一个复杂问题是怎么得到解的，因为我们知道这些问题本质上就是P问题，一些喜欢研究问题解法的人可能会继续探索问题解决的过程，但这对于问题被解决这一事实没有任何影响。

在这样的世界里，所有益智类游戏将失去探索的乐趣，因为最优解已经找到，这些游戏会变得像小学乘法一样只剩下公式化的解答。所有的科学学科都会得到长足发展，但大部分的加密算法将不再有效，数学的研究主题将变成“提出问题”而非“解决问题”，AI将会轻易通过图灵测试。最后，我们将无法想象这个新世界还会有哪些翻天覆地的变化……

References

• http://www.matrix67.com/blog/archives/2552

• https://www.bilibili.com/video/BV11W411H7YU