P: 可以用一個明確的演算法在polynomial time來解決.
NP: 無法用一個明確的演算法在polynomail time來解決,
但可以在polynomail time來驗證所找的答案是對的或錯的,
亦即NP 就是無法以一般的 algo 找到 ploy time 解法,
但是用 guess and check(即任猜一個答案) 的方法來在 Polynomail time verify
這個 answer 是否正確.
NP-Hard: NP問題裡頭最難的稱之(先這樣子解釋, 因為現階段扯到reduce的觀念會太深).
NP-Complete: NP 和 NP-Hard 兩者之交集.
記法=> 你是全班最帥的 = 你是這個班上的人 且 你是金城武
再來是搞純理論的人目前都想知道的結果, 目前還沒有人證出來的 =>
若有一 NPC 問題可找到 Poly time 之解, 則 NP = P.
這個結果很震撼吧, 如果證得出來的人就是本世紀的大師啦.
※ 編輯: flashstar 來自: 61.224.77.77 (06/14 20:18)