;
如果
\rm P = NP
, 则三者关系如下图右边所示 ;
二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]
----
该观点目前认为是错误的 , 不过没有严格的证明..., 不满足第一个条件的问题 ,
\rm NP
中的任何计算问题 , 难易程度 , 都不会超过当前的 计算问题
\rm B
, 则称
\rm B
是
\rm NP
难 的 ;
\rm NP...难 问题包含了
\rm P = NP = NP
-完全 这三种问题 ;
三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]
----
该观点目前认为是正确的 , 同样也没有严格的证明...;
证明
\rm NP
完全的意义 :
如果能够证明 计算问题
\rm A
是
\rm NP
完全的 ,
\rm NP
完全问题 与
\rm P
问题 不相交 ,
说明 该 计算问题...\rm A
一定没有有效算法 , 只有有效算法才会在
\rm P
中 ,
因为 没有任何有效算法在 是
\rm NP
完全的 ;
如果 计算问题 是
\rm NP
完全的 , 该算法一定不是有效算法