文章目录

一、NP 完全的定位二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]

一、NP 完全的定位

计算理论中三个重要概念 :P\rm PP , NP\rm NPNP , NP\rm NPNP 完全 ;

P\rm PP , NP\rm NPNP , NP\rm NPNP 完全 , 三者的相互关系如下 :

目前 P\rm PP 与 NP\rm NPNP 的是否相等不确定 , 只知道 P≤NP\rm P \leq NPP≤NP ;

如果 P≠NP\rm P \not= NPP​=NP , 则有 P<NP\rm P < NPP<NP , 三者关系如下图左边所示 ;

如果 P=NP\rm P = NPP=NP , 则三者关系如下图右边所示 ;

二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]

该观点目前认为是错误的 , 不过没有严格的证明 ;

P=NP\rm P = NPP=NP 情况分析 : 如果 P=NP\rm P = NPP=NP , 则有 P=NP=NP\rm P = NP = NPP=NP=NP-完全 ;

NP\rm NPNP 难问题就是 满足 NP\rm NPNP 完全问题的第二个条件 , 不满足第一个条件的问题 ,

NP\rm NPNP 中的任何计算问题 , 难易程度 , 都不会超过当前的 计算问题 B\rm BB , 则称 B\rm BB 是 NP\rm NPNP 难 的 ;

NP\rm NPNP 难 问题包含了 P=NP=NP\rm P = NP = NPP=NP=NP-完全 这三种问题 ;

三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]

该观点目前认为是正确的 , 同样也没有严格的证明 ;

P≠NP\rm P \not= NPP​=NP 情况分析 :如果 P≠NP\rm P \not= NPP​=NP , 则有

P<NP\rm P < NPP<NP ,

NP\rm NPNP 完全 <NP\rm <NP<NP

NP\rm NPNP 问题 中包含了三种计算问题 :

① P\rm PP 问题

② NP\rm NPNP 完全问题

③ 其它问题 , 既不属于 P\rm PP 问题 , 又不属于 NP\rm NPNP 完全问题 ;

图同构问题 , 就属于 其它问题 , 既不属于 P\rm PP 问题 , 又不属于 NP\rm NPNP 完全问题 ;

NP\rm NPNP 难 问题 , 包含了 NP\rm NPNP 完全问题 , 不包含 P\rm PP 问题 和 NP\rm NPNP 中的其它问题 ;

证明 NP\rm NPNP 完全的意义 :

如果能够证明 计算问题 A\rm AA 是 NP\rm NPNP 完全的 , NP\rm NPNP 完全问题 与 P\rm PP 问题 不相交 ,

说明 该 计算问题 A\rm AA 一定没有有效算法 , 只有有效算法才会在 P\rm PP 中 ,

因为 没有任何有效算法在 是 NP\rm NPNP 完全的 ;

如果 计算问题 是 NP\rm NPNP 完全的 , 该算法一定不是有效算法 ;

【计算理论】计算复杂性 ( NP 完全问题 | NP 难 问题 P = NP 的情况 | NP 难 问题 P ≠ NP 的情况 )