文章目录
一、NP 完全的定位
二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]
三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]
一、NP 完全的定位
计算理论中三个重要概念 : P \rm PP , N P \rm NPNP , N P \rm NPNP 完全 ;
P \rm PP , N P \rm NPNP , N P \rm NPNP 完全 , 三者的相互关系如下 :
目前 P \rm PP 与 N P \rm NPNP 的是否相等不确定 , 只知道 P ≤ N P \rm P \leq NPP≤NP ;
如果 P ≠ N P \rm P \not= NPP
=NP , 则有 P < N P \rm P < NPP<NP , 三者关系如下图左边所示 ;
如果 P = N P \rm P = NPP=NP , 则三者关系如下图右边所示 ;
二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]
该观点目前认为是错误的 , 不过没有严格的证明 ;
P = N P \rm P = NPP=NP 情况分析 : 如果 P = N P \rm P = NPP=NP , 则有 P = N P = N P \rm P = NP = NPP=NP=NP-完全 ;
N P \rm NPNP 难问题就是 满足 N P \rm NPNP 完全问题的第二个条件 , 不满足第一个条件的问题 ,
N P \rm NPNP 中的任何计算问题 , 难易程度 , 都不会超过当前的 计算问题 B \rm BB , 则称 B \rm BB 是 N P \rm NPNP 难 的 ;
N P \rm NPNP 难 问题包含了 P = N P = N P \rm P = NP = NPP=NP=NP-完全 这三种问题 ;
三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]
该观点目前认为是正确的 , 同样也没有严格的证明 ;
P ≠ N P \rm P \not= NPP
=NP 情况分析 : 如果 P ≠ N P \rm P \not= NPP
=NP , 则有
P < N P \rm P < NPP<NP ,
N P \rm NPNP 完全 < N P \rm <NP<NP
N P \rm NPNP 问题 中包含了三种计算问题 :
① P \rm PP 问题
② N P \rm NPNP 完全问题
③ 其它问题 , 既不属于 P \rm PP 问题 , 又不属于 N P \rm NPNP 完全问题 ;
图同构问题 , 就属于 其它问题 , 既不属于 P \rm PP 问题 , 又不属于 N P \rm NPNP 完全问题 ;
N P \rm NPNP 难 问题 , 包含了 N P \rm NPNP 完全问题 , 不包含 P \rm PP 问题 和 N P \rm NPNP 中的其它问题 ;
证明 N P \rm NPNP 完全的意义 :
如果能够证明 计算问题 A \rm AA 是 N P \rm NPNP 完全的 , N P \rm NPNP 完全问题 与 P \rm PP 问题 不相交 ,
说明 该 计算问题 A \rm AA 一定没有有效算法 , 只有有效算法才会在 P \rm PP 中 ,
因为 没有任何有效算法在 是 N P \rm NPNP 完全的 ;
如果 计算问题 是 N P \rm NPNP 完全的 , 该算法一定不是有效算法 ;
