P,NP,NPC,NP-Hard,co-NP问题辨析

港控/mmm° 2023-10-06 06:25 9阅读 0赞

学算法学到这章，真是神仙打架。上网学习各位前辈的文章，看的我也是眼花缭乱。终于看到一篇易于理解的（网址附于文末），看过之后写写自己的理解。如有错误，请各位前辈指正！

**P问题**，在这里不说全称了，感觉说了也没用。P问题就是指能在多项式时间求解出的问题。举个例子：排序问题，二分查找问题的时间复杂度分别是O（nlogn）,O(logn)。

说到时间复杂度，这篇文章对此也做了详细的解释，成功刷新了我对于时间复杂度的理解，原文如下，再次引用：

“时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。”

**NP问题**就是不能确定是否能够在多项式时间内找到一个解。但若给出一个解，能在多项式时间内证明这个解是否正确（学名叫判定性问题）。定义的前半句有两层含义：可能找得到解，也可能找不到解。找得到解问题就变成了P问题。所以P问题属于NP问题(P问题是NP问题的真子集)

**NPC问题**，说到NPC问题，就要提到一个操作叫“规约”。这里有一个易受误导的地方，规约不是越化越简单，反而是越化越难。举个例子：A是求解一元一次函数，B是求解一元二次函数。可以说A可规约至B，因为会解B，一定会解A。可把A看作是二次项系数为0的B。所以，每规约一步，问题就变得越复杂。规约具有传递性：A规约至B，B规约至C，那么A规约至C。问题来了，那么一直规约下去会得到什么呢？这就是NPC问题！

NPC问题上文有所介绍，它是由NP问题不断规约得来。首先NPC本身是一个NP问题，这是证明一个问题是NPC问题的首要条件。有NPC和NP问题之间的关系，可以看出：如果一个NPC问题得到了证明，那么所有可以规约至该NPC的NP问题都得到了证明。到目前为止，部分NPC问题得到了证明，但还有很多未证明。也有人把这些问题称之为信息学的“巅峰”。（一猜也知道是很难的！）下面介绍一下证明一个问题是NPC问题的方法：

第一步：证明这个问题是一个NP问题

第二步：证明一个已知的NP问题能够规约到该问题。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dsc19udWFh_size_16_color_FFFFFF_t_70]

**NP-Hard问题**，就是满足NPC问题的第二个条件，但是却不一定满足第一个条件的问题。任意NP问题都可以在多项式的时间内规约至NP-Hard问题。但像上文说的，NP-Hard问题不一定是NP问题。通俗点说，NP-Hard问题就是至少和NPC问题一样难。可能是NPC也可能不是NPC（这取决于NP-Hard问题是否为NP问题）。

**Co-NP问题**是由补问题属于NP问题的问题组成。对于co-NP问题上网差了一些资料。主要的研究方向好像是co-NP问题和NP问题的关系。鉴于水平有限，实在是看不懂，就此作罢！还望高手指点。

最后贴一张书上的图，说明各类问题之间的关系：  
![在这里插入图片描述][20200502003416165.png]  
参考网址：blog.sina.com.cn/s/blog\_53bbb4b90101ckkq.htmllink  
（该网址的主人也是转载的，原主人的网址有权限。无法访问，请原主人谅解）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dsc19udWFh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2021011116205944.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dsc19udWFh,size_16,color_FFFFFF,t_70
[20200502003416165.png]: https://img-blog.csdnimg.cn/20200502003416165.png