P问题、NP问题、NPC问题和NP-Hard问题，相关概念与题目

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-完全问题的证明，是从精确覆盖问题归约到背包问题（背包更加复杂和一般化），因此背包问题列为精确覆盖问题的子项。
  
  

参考资料：

• https://www.cxyxiaowu.com/9424.html
• https://neusncp.com/user/blog?id=57
• http://www.coderjie.com/blog/0d2fa4b2693711e8841d00163e0c0e36
• https://zhuanlan.zhihu.com/p/53085012
• https://durant35.github.io/2017/06/08/Algorithms_NP-Complete(I)/
• https://blog.csdn.net/l_mingo/article/details/54232382
• https://zhuanlan.zhihu.com/p/102362515