所有的參考來自:
What are the differences between NP, NP-Complete and NP-Hard?
決策問題: 可以用是, 或者否來回答的問題.
什么是P
多項式時間內(nèi)可以求解的問題的集合.
什么是NP
表示所有決策問題的集合, 并且可以在多項式時間內(nèi)驗證.
什么是NPC
是NP的子類, 可以在多項式的時間內(nèi)將所有的NP問題歸約為NPC問題. 這個子類稍微有點特殊, 其特殊性表現(xiàn)在:
- 所有的NP問題都可以在多項式時間內(nèi)歸約為它們;
- 它們本身是一類NP問題;
- 解決了這個問題, 那就意味著NP問題都可以得到解決了.
可以這樣理解NPC問題是NP問題的典型, 解決了它們, NP問題就解決了.(要抓就抓典型)
什么是NP難(NP-Hard)
直觀的說, 這些問題至少和np問題一樣困難(困難程度: NP難 >= NP).
精確的定義X是NP難問題, NPC問題Y可以在多項式時間內(nèi)歸約為X. (這里的X, 不一定是NP問題, 如果X==NP, 那么NP難就是NPC了)
也就是說, 只要在多項式時間內(nèi)解決了一個NP難問題, 那么所有的NPC問題都可以在多項式時間內(nèi)解決了, 那么也就是說所有的NP問題都可以在多項式時間內(nèi)解決了.
需要注意的是, NP難問題不一定是 NP 問題, 而且它們不一定是決策問題.
p, np, npc, np難關(guān)系圖
還有一個表幫助理解:(難度從上倒下, 依次增大)
| 問題類型 | P時間內(nèi)可驗證 | P時間內(nèi)可以求解 |
|---|---|---|
| P | Yes | Yes |
| NP | Yes | Yes or No * |
| NPC | Yes | Unknown |
| NP難 | Yes or No ** | Unknown *** |
注解:
* 當一個P問題的NP問題, 可以在P的時間內(nèi)解決. (因為P是NP的子集)
** 當一個NP難問題是一個NPC問題的時候, 可以在P時間內(nèi)驗證
*** NP-Complete problems (all of which form a subset of NP-hard) might be. The rest of NP hard is not.
