NP问题真的很难理解。

希望通过这篇文章，不仅计算机相关的专业人士能理解和区分什么是P型问题，什么是NP型问题，非专业人士如学文科的朋友也能有一定程度的理解。

程序员领域有个笑话，就是有个哥们去google面试的时候，被问到一个问题:什么情况下P=NP，然后他的回答是“当N=1”。这是我第一次听说P=NP问题，大概是临近毕业准备找工作的时候。

这几天科技新闻头条都被阿尔法狗大战李世石给炸了。虽然我不是AI专家，但我也想写点东西，从普通人的角度谈谈这个有趣的事情。在收集资料的时候，又看到了NP问题，于是想休息一下，写一篇文章《AI玩法怎么走？之前，先说一下这个NP问题。

最简单的定义是:

p问题:

一个问题可以在多项式()的时间复杂度内解决。

NP问题:

一个问题的解可以在多项式时间内得到验证。

NP难问题:

任何np问题都可以在多项式时间内归结为这个问题，但问题本身不一定是NP问题。还原是指为了解决问题A，将问题A还原为另一个问题B，解决问题B也间接解决了问题A..

NPC提问:

既是NP问题，也是NP难问题。

这个定义虽然简单，但是对于第一次接触P和NP的人来说，就像前阵子问你什么是“引力波”你回答:引力波是时空的涟漪。我几乎没有从回答中得到任何有意义的理解。所以希望不仅是计算机相关的专业人士能看懂内容，文科生也能在一定程度上看懂。

现阶段，虽然电脑已经非常普及，有人用它来上网、玩游戏、看电影，但仍然很少有人在意，电脑的本质就是电脑，在展示其巨大计算能力的同时，给人们的日常生活带来娱乐和便利。我们日常生活中使用的各种软件，其实都是一套计算机程序，程序可以看作是一系列的算法，而我们看到的计算机硬件的作用就是处理这些算法。这里所说的算法不仅仅是简单的加减乘除，而是包括以下要素:

算术运算:加、减、乘、除等运算。

逻辑运算:或、与、非等。

关系运算:诸如大于、小于、等于和不等于等运算。

数据传输:输入、输出、赋值和其他操作。

以及通过控制结构控制处理这些操作的顺序。说到这里，我有点担心有些朋友不太理解。举个例子吧。

我们如何从n个数字中挑出最大的数字？让我们简单点。我们只需要一个一个的比较。具体来说，比较N和n-1，记下较大的数。然后我们将这个数与n-2进行比较，记下较大的数，以便与最后一个数进行比较。这整个比较过程可以称之为一个算法，这个算法就包含了上述要素。给我们的数n是算法的输入数据，我们要选取的最大数是算法的输出数据。其中在判断大小的时候一定要用到一些基本的算术运算或者关系运算。

这里希望大家能基本明白什么是算法，因为我会花一点时间讲算法的时间复杂度是多少。计算或解决一个问题，问题通常有一个大小尺度，用N来表示，我们参考上面的例子，从N个数中找出最大的数。这个N就是问题的大小。怎么找？我们要比较n-1次才能得到结果，这个n-1次可以理解为花费的时间，也就是时间复杂度。再比如，n的个数从最大到最小排序，n是它的标度。如果按照这样的方法:第一次从n的个数中求最大，第二次从n-1的个数中求最大，以此类推，所需的比较次数为n(n-1)/2。我们用的方法叫做算法，所以n(n-1)/2就是算法的时间复杂度。对于时间复杂度，当n足够大时，我们只关注最高次幂项，其他项可以忽略。另外它的常系数并不重要，我们只关注n(n-1)/2的平方，这是这个问题时间复杂度的专业表达。

事实上，时间复杂度并不是指一个程序解决一个问题需要多少时间，而是指当问题规模扩大时，程序所需的时间长度增加得有多快。也就是说，对于一台高速处理数据的计算机来说，处理一个特定数据的效率并不能衡量一个程序的好坏，而应该取决于这个数据的规模变成几百倍之后，程序的运行时间是否还一样，或者是变慢了几百倍、几万倍。不管数据有多大，程序的处理时间总是那么多，所以我们说程序很好，有时间复杂度，也叫恒定复杂度；这个程序的时间复杂度是，比如求n个数的最大值；比如冒泡排序、插入排序等。，数据扩展2倍，时间变慢4倍，属于复杂度。还有一些穷举算法，所需时间呈几何级数增长，是指数级复杂度甚至阶乘复杂度。不会有复杂度，因为前面的“2”是一个系数，根本不会影响整个程序的时间增长。同样，的复杂性也是的复杂性。所以我们会说一个新程序的效率比后者低。虽然在n较小时前者优于后者，但后者随着数据规模增长缓慢，最终复杂度会远远超过。我们还说的复杂度小于的复杂度。

好了，该说重点了。很容易看出，前面的时间复杂度类型可以分为两个层次:一个是，，，等。我们称之为多项式级复杂度，因为它的尺度n出现在底数；另一种是非多项式级别的和复杂度，其复杂度往往是计算机无法承受的。

是时候介绍一下P问题和NP问题的概念了:如果一个问题能在多项式的时间复杂度内找到能解决它的算法，那么它就属于P问题。对NP问题的理解不是NotP，NP问题也不是非P问题。NP问题是指一个解可以在多项式时间内被验证的问题。NP问题的另一个定义是可以在多项式时间内猜测出一个解。我相信没有必要举太多例子来说明P型问题。上面说的问题，比如求最大数，排序，都是P型问题，需要再举一个例子才能更好的理解NP问题。

大整数的因式分解——比如有人告诉你，9938550这个数可以分解成两个数的乘积，你不知道对不对，但是如果告诉你这两个数是1123和8850，用最简单的计算器就可以很容易地验证。

最短路径问题——最短路径，即沿着图的边从一个顶点到另一个顶点的路径中，每边权重之和最小的路径。

如上图，比如我告诉你从0点到5点的最短路径是22，我只需要0->来验证。1，加上1->；5，13+9 = 22，时间复杂度不变。如果从上图的6个点展开到n个点，验证过程所需的算法时间也是非常异构的。如果不告诉你最短路径有多重要，需要用算法求解，我们可以这样“猜”出它的解:先找一个总距离不超过100的方案，假设我们能“猜”出一条运气极好的路线，使总长度不超过100，那么我们每次只需要猜一条路n次。接下来要找一个总长度小于50的方案。如果找不到，我们就把门槛提高到75...假设我们最终找到一个总长为90的方案，但是找不到一个总长小于90的方案。我们最终“猜到”这个旅行商问题的解是一条多项式时间长度为90的路线。

有没有一个不是NP难的问题？是的。正是对于这些问题，验证解不能在多项式时间复杂度内完成。比如问:一个图中没有哈密尔顿圈吗？

从图中的任意一点出发，最后回到起点，成为哈密顿回路当且仅当它经过图中的每一个节点一次。

验证哈密尔顿回路，我们只需要在给定的路径上走一遍，看每个节点是否只经过一次，而验证不存在哈密尔顿回路，我们需要每条路径走一遍，否则不敢说不存在哈密尔顿回路。

之所以要专门定义NP问题，是因为对于那些无法用多项式时间复杂度验证的问题，我们不会试图用多项式时间复杂度去寻找它的解，这有点别扭，但是看了几遍应该就明白了。一般来说，把一个问题的答案告诉你，让你去验证，需要很长时间，这可以比喻成用一个算法去求解，肯定需要更长的时间。

那么反过来说，所有的P问题都是NP问题。也就是说，如果你能解出一个问题多项式，你就一定能验证一个问题多项式的解——既然所有的正解都出来了，那么只需要比较任意一个给定的解，只需要用多项式时间复杂度再给你算一次。关键是人们想知道是否所有的NP问题都是P型问题，即是否所有可以在多项式时间内验证的问题也可以在多项式时间内求解。我们可以从集合的角度来解释。如果所有P类问题归入一个集合P，所有NP类问题归入另一个集合NP，那么显然有P个属于NP。现在所有关于NP问题的研究都集中在一个问题上，就是有没有P=NP？所谓“NP问题”，其实就是一句话:证明或推翻P=NP。

说到这里，什么是P型问题，什么是NP型问题就结束了。可能会有一些人不是很清楚，那我们就用通俗但不是很严谨的表述来概括一下吧。

p型问题是指那些答案容易被计算机算出的问题。

NP类问题是指那些答案已知后，很容易被计算机验证的问题。

接下来进入的话题是为什么P=NP很难证明。看它无聊就好。至少你可以区分P和NP。接下来的内容会更烧脑。

我们先来看一个集合图，它反映了P=NP或者P！=NP，其中出现了两个新概念NP-Hard和NPC。要解释为什么至今没有P是否等于NP的结论，我们得先搞清楚NPC和NP-Hard。

在介绍NPC之前，我们先来学习一个概念——归约。简单来说，一个问题A可以归结为一个问题B，也就是说问题A可以通过问题B的解来解决，或者说问题A可以“变成”问题B..比如有两个问题:解一元一次方程，解一元二次方程。那么我们说前者可以化简为后者，因为我们知道如何解一元二次方程，所以一定可以解一元二次方程，因为二次方程是二次系数为零的二次方程。“问题a可以化简为问题b”，这样就很好理解了，问题b比问题a难，解决问题b的时间复杂度应该大于或等于解决问题a的时间复杂度，而且化简还有一个重要的性质:传递性。如果问题A可以归结为问题B，问题B可以归结为问题C，那么问题A一定可以归结为问题C，这应该很好理解。现在来说说归约的标准概念:如果能找到这样一个变化规律，使得任意一个程序A的输入都可以按照这个规律转化为程序B的输入，使得两个程序的输出都是相同的，那么我们说问题A可以归约为问题B。

从归约的定义可以看出，一个问题归约到另一个问题，时间复杂度增加，问题的应用范围也增加。通过对一些问题的不断约简，可以不断寻找复杂度更高但适用范围更广的算法来替代那些复杂度低但只针对小类问题的算法。那么如果一个NP问题不断约简，最后有没有可能找到一个时间复杂度最高的“所有NP问题”的超级NP问题呢？答案其实是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以归结为它，而且不仅是一个问题，还有很多问题，而且是一类问题。这类问题就是传说中的NPC问题，是NP完全的。所以NPC问题的定义很简单。满足以下两个条件的问题就是NPC问题。首先，一定是NP问题；那么，所有的NP问题都可以归结为它。

由于所有的NP问题都可以归结为NPC问题，只要任何一个NPC问题找到一个多项式算法，所有的NP问题都可以用这个算法求解，所以NP等于P，所以目前NPC问题没有有效的多项式算法，只能用指数甚至阶乘复杂度算法求解，也就是说如果我们能找到一个可以用多项式时间复杂度求解的NPC问题，就证明P=NP。

而说到NP难的问题。NP-Hard问题是一类满足NPC问题的第二个定义但不一定满足第一个定义的问题，即所有的NP问题都可以归结为它，但不一定是NP问题，即即使有一天找到了NPC问题的多项式算法，NP-Hard问题也不能用多项式算法求解，因为它不是NP问题，很难验证答案。

下面是Matrix67文章中的一个逻辑电路的例子来说明NPC问题。

逻辑电路问题是指这样一个问题:给定一个逻辑电路，问是否存在使输出为真的输入。

什么是逻辑电路？一个逻辑电路由几个输入、一个输出、几个“逻辑门”和许多导线组成。看看下面这个例子，不用解释你马上就明白了。

这是一个相对简单的逻辑电路。当输入1，输入2，输入3分别为真，真，假或假，真与假时，输出为真。

有没有一个逻辑电路的输出无论如何都不可能是真的？是的。这里有一个简单的例子。

上面这个逻辑电路，不管输入是什么，输出都是假的。假设这个逻辑电路没有一组使输出为真的输入。

回到上面，给定一个逻辑电路，问是否存在使输出为真的输入，这就是逻辑电路问题。

逻辑电路问题属于NPC问题。这是严格证明的。它显然属于NP问题，可以直接证明所有NP问题都可以归结为它。证明过程相当复杂，大致意思是任何NP问题的输入输出都可以转化为一个逻辑电路的输入输出(考虑到计算机内部只有0和1的一些运算)，所以对于一个NP问题，问题转化为寻找一个满足真结果的输入(即可行解)。

像这样的NPC问题，目前还没有可以多项式复杂度求解的算法，所以一旦这类问题变成多项式复杂度可解，很多问题就可以用现有的计算机技术解决了。就像计算机下围棋，验证一盘棋的结果显然很简单，但要保证每一局都能赢，目前的方法需要计算机枚举所有的可能性，根据每一步棋的变化搜索出最终获胜的棋路，目前的计算机性能显然是达不到的。因为围棋的状态空间复杂度达到了10的172平方，围棋的博弈树复杂度达到了10的300次方，所以只看数字可能不太直观。总之，围棋改变的已经超过了宇宙的原子数量！

所以，对于围棋这样的游戏，人工智能要想打败人类，需要达到以下两个条件中的任意一个:

电脑性能无限强大，可以穷尽一切可能；

提出了一种新的算法，可以保证在不穷举的情况下获胜；

目前谷歌的AlphaGo所做的只是通过优化算法来提高穷举搜索的效率，同时利用现有的大数据和云计算来提高计算性能。下一篇文章将更详细地介绍AI游戏是如何进行的，敬请关注。