姜咏江

为了理解好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。