| title | date | tags |
|---|---|---|
NP问题理解 |
2018-10-02 09:53:50 -0700 |
NP问题 |
P问题、NP问题、NP难问题、NP完全问题
一个问题可以在多项式（O(n^k)）的时间复杂度内解决。
时间复杂度如(n^2, n^4, n(log(n)))都是多项式时间的，指数级别的如(2^n，n^n)这些就不是多项式时间了。
给定一个解，我们可以在多项式时间内检查他正确与否的决策问题，为NP问题。
之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。
很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。
NP-hard问题：所有的NP问题都可以约化到它。
NP-hard问题是这样的问题，只要其中某个问题可以在P时间内解决，那么所有的NP问题就都可以在P时间内解决了。NP-c问题就是NP-hard问题。但注意NP-hard问题它不一定是NP问题，比如，下围棋就是NP-hard问题，但不是NP问题，我们要在一个残局上找一个必胜下法，告诉我们下一步下在哪里。显然，我们找不到这个解，而且更难的是，就算有人给我了一个解，我们也无法在P时间内判断它是不是正确的。
**任意NP问题都可以在多项式时间内归约为该问题，但该问题本身不一定是NP问题。**归约的意思是为了解决问题A，先将问题A归约为另一个问题B，解决问题B同时也间接解决了问题A。
为了说明NPC问题，引入--约化(规约)概念。
一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。
《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。
“问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。 从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。
NP-c问题是这样的一类问题，首先他是属于NP的，而且他是NP问题里面最难解决的问题。难到什么程度？只要其中某个问题可以在P时间内解决，那么所有的NP问题就都可以在P时间内解决了。
NP-C问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。
既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P了。因此，给NPC找一个多项式算法太不可思议了。
NP-C问题既是NP问题，也是NP-hard问题。
P问题属于NP问题，NP-C问题属于NP问题。
NP-C问题同时属于NP难问题，是NP与NP难问题的交集。
参考：
什么是NP问题，什么是NP hard问题，什么是NP完全问题 https://blog.csdn.net/u013089961/article/details/50069779
P、NP、NPC和NP-Hard相关概念的图形和解释： https://blog.csdn.net/huang1024rui/article/details/49154507