https://zhuanlan.zhihu.com/p/131585177
NP问题
既然说到了NP问题，简单和大家聊聊NP问题的定义。
很多算法的初学者对于这些概念非常迷糊，也的确，这些概念听起来都差不多，的确很容易搞晕。我们先从最简单的开始介绍，首先是P问题。
P问题可以认为是已经解决的问题，这个解决的定义是可以做多项式的时间复杂度内解决。所谓的多项式，也就是O(n^k)，这里的k是一个常数。与多项式相反的函数有很多，比如指数函数、阶乘等等。
NP问题并不是P问题的反义，这里的N不能理解成No，就好像noSQL不是非SQL的意思一样。NP问题指的是可以在多项式内验证解的问题。
比如给定一个排序的序列让我们判断它是不是有序的，这很简单，我们只需要遍历一下就好了。再比如大整数的因式分解，我们来做因式分解会很难，但是让我们判断一个因式分解的解法是不是正确则要简单得多，我们直接把它们乘起来和原式比较就可以了。
显然所有P问题都是NP问题，既然我们可以多项式内找到解，那么必然我们也可以在多项式内验证解是否正确。但是反过来是否成立呢，是否多项式时间内可以验证解的问题，也可以通过某种算法可以在多项式时间内被解开呢？究竟是我们暂时还没有想到算法，还是解法一开始就不存在呢？
上面的这个问题就是著名的NP=P是否成立的问题，这个问题目前仍然是一个谜，有些人相信成立，有些人不相信，这也被认为是二十一世纪的最大难题之一。
为了证明这个问题，科学家们又想出了一个办法，就是给问题做规约。举个例子，比如解方程，我们解一元一次方程非常简单，而解二元一次方程则要困难一些。如果我们想出了解二元一次方程的办法，那么必然也可以用来解一元一次方程，因为我们只需要令另一个未知数等于0就是一元一次方程了。
同理，我们也可以把NP问题做转化，将它的难度增大，增大到极限成为一个终极问题。由于这个终极问题是所有NP问题转化得到的，只要我们想出算法来解决了终极问题，那么，所有的NP问题全部都迎刃而解。就比如如果我们想出了解N元方程的算法，那么这一类解方程的问题就都搞定了。这种转化之后得到的问题称为NP完全问题，也叫做NPC问题。
下面我们来看一个经典的NPC问题，即逻辑电路问题。
下图是一个逻辑电路，假设我们知道它的输出是True，我们也知道了电路的结构，那么请问我们能否确定一定可以找到一个输入的组合，使得最后的输出是True吗？
它显然是一个NP问题，因为我们可以直接把解法代入电路去计算一下，就可以验证这个解是否正确，但是想要得到答案却很难。经过严谨的证明，所有NP问题都可以经过转化得到它，也就是说如果我们找到一种解法可以在多项式内解决这个问题，那么我们就解决了所有的NP问题。
最后，还有一个NP-Hard问题，NP-Hard问题是说所有NP问题可以经过转化得到它，但是它本身并不是NP问题，也就是说我们无法在多项式时间内判断它的解是否正确。
比如刚才提到的旅行商问题就是一个NP-Hard问题，因为即使我们给定了一个解，我们也没有办法快速判断给定的解是否正确，必须要遍历完所有的情况才可以。我们验证的复杂度就已经超出了多项式的范畴，所以它不属于NP问题，比NP问题更加困难，所以是一个NP-Hard问题。
