文章目录
1、概念理解2、相关题目1、概念理解
背景知识：
多项式时间：我们知道时间复杂度有O(1)，O(n)，O(logn)，O(n^a)，O(a^n)，O(n!)等，我们把O(1)，O(n)，O(logn)，O(n^a)等称为多项式级的复杂度，我们把O(a^n)，O(n!)称为非多项式级的复杂度。非多项式级的复杂度在数据量变大后，需要的时间迅速增长。约化：问题A约化为问题B的含义就是，可以用问题B的解法解决A。（变成更复杂更一般化的问题）
例如我们有问题A：求解一元一次方程bx+c=0，问题B：求解二元一次方程ax^2+bx+c=0。
如果我们知道问题B的解法，那么一定可以知道问题A的解法，因为只要我们令a=0，问题B就和问题A等价，所以我们可以说“问题A可约化为问题B”。
很显然当我们说“问题A可约化为问题B”，那么问题B的时间复杂度一定高于或者等于问题A的时间复杂度。其次约化还具有一个重要性质：约化具有传递性。也就是说如果问题A可约化为问题B，问题B可约化为问题C，那么问题A一定可约化为问题C。
核心概念：
P问题：可以在多项式时间复杂度内解决的问题。（计算起来很快）NP问题：可以在多项式时间内验证它的解是否正确。（算起来不确定快不快）NP-hard问题：所有NP问题都可以在多项式时间内约化到它的问题。NP-complete问题：即NPC问题，属于NP问题，且属于NP-hard问题。
所有NP问题都可以在多项式时间内约化到它并且它本身就是一个NP问题的问题。
问题之间的关系
P问题：排序问题就是一个P问题，因为我们有时间复杂度为O(n^2)的冒泡排序算法。NP问题：哈密顿回路问题，目前没有多项式时间的算法找到哈密顿回路，但我们很容易判断一个回路是否是哈密顿回路(看是不是所有顶点都在回路中，并且路径不重复)。NPC问题：我们知道一个问题约化后，时间复杂度可能增加了，问题的应用范围也可能增大了。那么通过不断的约化，我们能否找到一个超级NP问题，使得所有的NP问题都可以约化到它？答案是肯定的，这就是NPC问题。可以想象如果我们解决了NPC问题，那么所有的NP问题都将被解决。
此外NPC问题事实上不只一个，它有很多个，这是一类问题。很显然NPC问题是可以相互约化的，也就是说如果我们想证明一个问题是NPC问题，只要证明这个问题是NP问题并且已知的一个NPC问题可以约化到它。
NPC问题是怎么来的？布尔逻辑的可满足性问题(SATISFIABLITY problem)，简称为SAT，这是历史上第一个被证明的NPC问题。有了第一个NPC问题，一大堆NPC问题就出现了。事实上上文说的哈密顿回路问题就是一个NPC问题。P=NP ?（即是否能多项式复杂度解决任意一个NPC问题）
现在人们特别想知道P是否等于NP，也就是说是否所有的NP问题都可以在多项式时间内解决。目前P=NP即不能被证明也不能被推翻，事实上我们只要能在多项式时间内解决NPC问题，那么所有的NP问题都可以在多项式时间内解决，也就是P=NP，然而目前已知的NPC问题都没有找到多项式时间的解法。所以现在人们主流认为P不等于NP。NP难问题（NPH问题）：
它满足NPC问题定义的第二条但不一定要满足第一条，即所有的NP问题都能在多项式时间内约化到它，同时它不一定是一个NP问题。
最具代表性的NP-Hard问题：TSP, 著名的推销员旅行问题。背袋问题（甲）。包装问题。舞伴问题。库存问题等等。P问题是NP问题的子集，NPC问题是NP问题的终极。NP-Hard问题是NPC问题的猜想（它本身不是一个NP问题，但是他可以解决所有的NP问题）
2、相关题目
目前求解NP难问题的常见方法
（1） 特殊情形：仔细分析所遇到的NP完全问题，研究具体实例的特殊性，考虑是否必须在最一般的意义来解此问题。也许可利用具体实例的特殊性，在特殊条件下解此问题。许多NP完全问题在特殊情形下可以找到多项式时间算法。例如求图G的最大团问题（典型描述，给定一个图G，要求G的最大团，团是指G的一个完全子团，该子团不包含在任何其他的完全子图当中，最大团指其中包含顶点最多的团）是NP完全问题，而在图G是平面图的情形下，该问题是多项式时间可解的。（2） 动态规划和分枝限界方法：对于许多NP完全问题来说，用动态规划和分枝限界方法常可得到较高的解题效率。（3） 概率分析：对于许多NP完全问题，其困难实例出现的概率很小，因此对这类NP完全问题常可设计出平均性能很好的算法。（4） 近似算法：通常可以设计出解NP完全问题的多项式时间近似算法，以近似解来代替最优解。
证明NPC问题
要证明npc问题的思路就是：先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它。《算法概论》练习题8.3
首先，因为String SAT的解可以在多项式时间内验证，所以属于NP问题， 另外， 可以将SAT归约到STRING SAT（将k设置成总个数）， 所以STRING SAT是NP完全问题SAT 问题解法
几个常见的NPC问题
卡普的21个问题列表如下，多数以问题的原名，加上巢状排版表示出这些问题归约的方向。
举例，背包问题（Knapsack）是NP-完全问题的证明，是从精确覆盖问题归约到背包问题（背包更加复杂和一般化），因此背包问题列为精确覆盖问题的子项。
参考资料：
/9424.html/user/blog?id=57/blog/0d2fa4b2693711e8841d00163e0c0e36/p/53085012https://durant35.github.io//06/08/Algorithms_NP-Complete(I)//l_mingo/article/details/54232382/p/102362515
