[演算](2008/06/18修正) P, NP, NPC, NP-hard
P是?
一個可以在O(n^k),k是一個常數,解出的問題
NP是?
非決定性多項式時間(non-deterministic polynomial time)
NP的問題是所有會回答"是"或"否"問題的集合,
而且,當它回答"是"的時候,答案確實是"是",而且可以在多項式時間被驗證.
當它回答"否"的時候,並沒有方法可以證明答案是不是正確的.
Nondeterministic algorithm
一個演算法具有一個或多個路徑選擇點,每個路徑都有可能會走
但沒任何方法知道會走哪一條
NPC是?
假如有個問題C滿足兩個條件
1.C屬於NP問題
2.任何的NP問題 can be reduced to C
定義C就是NPC的問題
意思是C就是NP集合中最難的問題.
NP-hard是?
假如有個問題H滿足
一個NPC的問題 can be reduced to H.
定義H是NP-Hard的問題
因為H至少要跟NP中最難的問題一樣難.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.7.59
→
05/26 16:02, , 1F
05/26 16:02, 1F
推
05/30 14:40, , 2F
05/30 14:40, 2F
推
05/30 14:42, , 3F
05/30 14:42, 3F
推
05/31 11:12, , 4F
05/31 11:12, 4F
→
05/31 11:12, , 5F
05/31 11:12, 5F
→
05/31 11:12, , 6F
05/31 11:12, 6F
※ 編輯: ajnightmare 來自: 58.114.208.7 (06/18 22:23)
※ 編輯: ajnightmare 來自: 58.114.208.7 (06/19 00:24)