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吗？