|||
姜咏江
为了理解好P与NP问题,特作图解释。
1. P、NP、NP-complete 和NP-hard之间的关系图
下面Fig.1是国外网站见到的P、NP、NP-complete 和NP-hard之间的关系图。因为没有归约表示,因而较难理解。
Fig. 1 Diagram for P, NP, NP-complete and NP-hard in case P≠NP.
Fig.2是我整理的P、NP、NP-complete 和NP-hard之间的关系图。图中用带箭头虚线表示归约关系,是否能够更好地理解?
Fig. 2虚线表示规约方向
从Fig.2科研看出,所有的NP问题(其中包括P问题)都可以通过多项式时间算法(程序过程)转化成NP-complete问题,转化的结果仍然是NP问题。
如果所有的NP问题都能转化为NP之外的问题,这些问题就是NP-hard问题。注意,整个平面都不是问题,因而应该认为除去这几种关注的问题之外,还有问题存在。
2. 为什么说P=NP-complete就有NP=P ?
从Fig.2不难看出,当P=NP-complete时,NP内的两个椭圆就合成了一个,即有所有的NP问题都可以在多项式时间内归约为P问题,也就有了“所有NP问题都可以在多项式时间内求出解”的结论。如此一来,当然NP=P了。
3. NP-hard
A problem A is NP-hard when every problem Lin NP can be reduced in polynomial time to A.
这是说,所有NP都能够在多项式时间归约到一个不属于NP的问题,这个问题就是NP-hard.
由Fig.2 你容易看到,如果NP-hard=P 就可以说明P=NP。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-26 15:01
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社