[Algorithms] P, NP, NP Complete, NP Hard

不是 Computer Science 本科生,還真是沒有辦法把 Complexity 懂得透徹。
一般我們用 P, NP, NP Complete 跟 NP Hard 來評估一個問題的複雜度,他到底是甚麼意思呢?

P: 指的是有 Polynomial Time 的解的問題。

NP: 指的是還沒有找到 Polynomial Time 的解,也不確定有沒有 Polynomial Time 的解,但是你一旦提供一個解,這個解可以在 Polynomial Time 被驗證的問題。

NP Complete: 指的也是還沒有找到 Polynomial Time 的解,但是可以在 Polynomial Time 被驗證的問題。但是NPC的問題是NP裡面比較難的問題,所以如果能夠證明NPC的問題有P的解,那NP的問題就都可以找到P的解。

NP Hard: 指的也是還沒有找到 Polynomial Time 的解,但是不確定是不是能在 Polynomial Time 被驗證的問題。NP Hard的問題又比NPC難。

一般來說 P 的問題算是比較簡單,NP Complete 跟 NP Hard 算是很難的問題。而 NP 的問題還是有可能找到快速算法。


Be the first to comment

Leave a Reply

Your email address will not be published.


This site uses Akismet to reduce spam. Learn how your comment data is processed.