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问题。