通俗易懂：P问题、NP问题、NPC问题和NP-hard问题

秒速五厘米 2022-12-20 02:59 409阅读 0赞

一、基础知识  
1.现实中的问题(比如：排序问题)，存在很多解决办法(即计算机领域的算法)，所以需要衡量算法的性能。

> 一个算法的优劣主要从算法的执行时间(即时间复杂度)和所需要占用的存储空间(即空间复杂度)两个方面衡量。

P类问题和时间复杂度有关，所以本文只谈时间复杂度。

2.时间复杂度  
若对排序算法有了解的小伙伴，大多是知道冒泡排序的平均时间复杂度为O( n 2 n^2 n2)，按照多项式的定义(形如 a n ⋅ x n + a n − 1 ⋅ x n − 1 + . . . + a 1 ⋅ x + a 0 a\_n·x^n + a\_\{n-1\}·x^\{n-1\} + ... + a\_1·x + a\_0 an⋅xn\+an−1⋅xn−1\+...\+a1⋅x\+a0的式子即为多项式)，所以排序问题存在时间复杂度为O( n 2 n^2 n2)的多项式时间算法，即排序问题属于P问题。

**二、P问题**  
存在多项式时间算法的问题。(P：polynominal，多项式)

> 当所需计算的数据量小时，人们察觉不到算法时间复杂度分别为O( n n n)与O( 2 n 2^n 2n)的差别，但当数据量达到数百万量级时，O( 2 n 2^n 2n)的算法可能需要让计算机算个几天，甚至数年。

时间复杂度排序 :  O ( 1 ) < O ( n ) < O ( log ⁡ 2 n ) < O ( n 2 ) < O ( n a ) < O ( 2 n ) ( a > 2 ) O(1) <O(n) < O(\\log\_2n) < O(n^2) < O(n^a) < O(2^n) (a > 2) O(1)<O(n)<O(log2n)<O(n2)<O(na)<O(2n)(a>2)

所以，研究时间复杂度是多项式的算法才有实际意义。

**三、NP问题**  
1.大整数分解  
比如：求大整数99400891的2个质因子是困难的，但是若告知9967、9973,验证它们是99400891的2个质因子是可以在多项式时间内实现的。

2.NP问题  
存在一类问题，不知道其是否存在多项式时间算法，但可以在多项式时间内验证一个猜测解的正确性。

> NP : Nondeterministic polynomial-time 非确定性多项式时间

四、千禧难题之首 : NP=P?  
有些科学家认为，所有的NP问题终究都可以在多项式时间内解决，只是我们暂时还没有找到方法；也有些科学家认为，某些NP问题永远无法在多项式时间内解决。

即千禧难题之首 :  N P = P   ? NP=P\\,? NP=P?1

> 如果证明了 N P = P NP = P NP=P就意味着所有的NP问题都可以通过计算机来解决，所以意义重大，不然怎么值100万美元呢(狗头.jpg)

**五、NPC问题**  
1.证明 N P = P   ? NP=P\\,? NP=P?思路之一 ：问题约化  
可以用问题B的算法来解决A ，我们就说问题A可以约化成问题B。  
**例如：**  
问题A :  3 x + 6 = 12 3x + 6 = 12 3x\+6=12 (采用一元一次方程的解法)  
问题B :  0 ⋅ x 2 + 3 x + 6 = 12 0·x^2 + 3x + 6 = 12 0⋅x2\+3x\+6=12 (采用一元二次方程的解法)  
显然问题A可以约化为问题B，如果证明了一元二次方程的解法是多项式时间算法，则说明一元一次方程的解法也是多项式时间算法。

> 约化具有传递性: A约化为B，B约化为C

**因此：**  
把众多的NP问题层层约化，必定会得到一个或多个“终极问题”，这些约化的终点就是所谓的NPC问题（NP-complete）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]  
2.NPC问题(2个条件)  
①自身是NP问题；  
②其他NP问题能约化到它；  
**即**：如果所有NP问题可在多项式时间内约化成**某个NP问题**，则该NP问题称为NP完全问题。

**六、NP-hard问题**  
满足NPC问题的条件②但不满足条件①。  
**即** : 如果所有NP问题可在多项式时间内约化成**某个问题**，则该问题称为NP难问题。

> 显然，NP-hard问题不一定是NP问题，可能是不可判定问题(图灵停机问题)

七、P问题、NP问题、NPC问题和NP-hard问题的关系  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center 1]  
八、参考文献

1.[P问题、NP问题、NP完全问题和NP难问题][P_NP_NP_NP]  
(旅行商问题被科学家证明属于NPC问题)

--------------------

1.  [Latex中的空格][Latex] ↩︎

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/957c1f2860ff418193788fc3929fc75f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/cac228cea53d43edbf684c01927fd14d.png
[P_NP_NP_NP]: https://blog.csdn.net/qq_21768483/article/details/80430590
[Latex]: https://blog.csdn.net/seaskying/article/details/51316607