5分钟简单理解P,NP,NPC,NPH

关于P, NP, NPC, NPH名词的解释, 网上的文章很多都是太长太专业或读不懂, 这里简单快速的整理一下我的理解,

可能不够专业准确, 但是能帮助你快速理解, 形成认知上的概念

为了理解这几个名词, 先要说明时间复杂度 和 多项式时间的概念

时间复杂度 与 多项式时间

时间复杂度O ( n ? ) O(n?)O(n?)用来评估算法的计算工作量的大小, 通常写成n的某种数学表达式, 其中n nn代表输入数据数量

它可以是多项式(常数乘法次方等)

1 ,n ,log n,n²,n³

也可以是非多项式(指数阶乘等)

2 ⁿ ,n!

其计算量层级大小关系如图,

O ( 1 ) < O ( log n ) < O ( n ) < O ( n log n ) < O ( n² ) < O ( n³ ) < O ( 2ⁿ ) < O ( n ! ) 

多项式形式就是我们中学数学用笔算的那些, 通常可以在有限的时间内计算出结果, 也叫做在多项式时间内解决

而非多项式的计算量, 会在n增大时爆发式增长,无法在有限的时间内纯靠跑完计算得出结果

举个简单的例子

假设n = 100 n=100n=100,

多项式n 2 = 10 0 2 = 10000 n^{2}=100^{2}=10000n2=1002=10000就是个口算题

非多项式2 n = 2 100 ≈ 1.26765 ∗ 1 0 30 2^{n}=2^{100}\approx1.26765*10^{30}2n=2100≈1.26765∗1030

这个数字有多大呢? 世界上最快的超级计算机(截止2020年11月TOP500数据)每秒计算量也才堪堪达到4.42 ∗ 1 0 17 4.42*10^{17}4.42∗1017, 大概要跑9万年, 这个计算量的算法肯定是不可取的

有了上面的概念, 我们来理解P, NP, NPC, NPH

P问题: 能找到在多项式时间里解决它的算法

能到找一个算法, 即使n很大, 也能在有限的时间内跑完, 求出最佳答案的

简单而言就是我们现在能算出最优解的,

NP问题: 能在多项式时间里验证它的答案

不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确

简单而言就是你随便瞎蒙个答案, 要判断这个答案对不对, 我还是能做到的

由上面两个概念可以得出:P ∈ N P P \in NPP∈NP

因为能多项式地解决一个问题，必然能多项式地验证一个问题的解

NPC(NP-Complete/NP完全)：

1. 所有的NP问题都可以reduce到某个问题C，

2. 且C是NP问题。

reduce是指Reducibility(约化/归约)，如果问题A可以约化为问题B，那么用B的解法就可以解决A（或者说问题A可以“变成”问题B）

也就是说如果NPC问题解决了（或者也叫做NPC问题发现了多项式级的算法），任意NP问题都可以套用该方法解决。NPC能强悍到能通解NP，那么它自然是NP问题中最难的那一部分。

NPH问题(NP-Hard/NP难)：

1. 所有的NP问题都可以reduce到某个问题H，

2. 但H不一定是NP问题。

即使NPC问题解决了，NPH问题有可能仍然无法得到多项式级的算法，也就是说NPH至少是NPC，甚至是比NPC更难的问题。

对于NP最终能否等于P，目前还是存在争议等待被验证的问题。

所以暂定P!=NP，则P, NP, NPC, NPH的关系图，根据之前的描述如下

2021-07-16 今天读到《数学之美》，附录里面就提到了于计算复杂度，依照里面的描述，略微补充之前的措辞。书里也同样也有一张和下图意思一致的插图(P!=NP情况下)。

就旅行商问题而言,

如果求解内容不同也可能变成不同问题