P,NP,NPC以及NP-Hard問題說明

這裡并不證明這些問題，也不涉及任何數學公式或者定理，單純以大白話說一下這幾類問題的差別與聯系

1.P類問題：能夠在多項式時間内解決的問題

2.NP類問題：能夠在多項式時間内驗證的問題，注意這裡的驗證。打個比方，旅行商問題求解最短路徑，我們給出一組資料，可以很容易的計算出路徑長度，但是并不能驗證是否是最短的，是以這并不是NP類問題，而且NP-Hard問題。當然，如果問題隻是要我們計算路徑長度，而非最短路徑，那麼這就是NP問題。

3.NPC問題：存在這樣一類NP問題，現如今并沒有多項式時間的解法，如果能夠證明他們在多項式時間内是能夠解決的，那麼其餘的NP問題就能在多項式時間内解決，換句話說就是這些問題可以推導出其他任何的NP問題。NPC問題首先必須要是NP問題。

4.NP-Hard問題：NP-Hard問題與NPC問題有點像，現如今并沒有多項式時間的解法，但是它并不要求是NP問題，注意是并不要求，而不是并非。所有的NPC問題都是NP-Hard問題，是以還有個說法就是NP-Hard問題是至少比NPC問題要難的問題。

如何用集合來表示的話，應該是如下關系（當然也可以用維恩圖來表示，這裡畫圖太麻煩了。。）：

P⊆NP

NPC⊆NP

NPC⊆NP-Hard

NP∩NP-Hard = NPC

網上有些維恩圖表示還是有問題的，從那些圖上看，NPC∩P = Ø，但實際結果未知，因為尚不能證明NP不等于P，而NPC又是一類NP問題