
P問題:可以用polynomial演算法解決的問題,亦即解決時間為polynomial時間。
(P.S. P問題可以用polynomial演算法解決,當然也可以用non-deterministic polynomial演算法解決,因此所有的P問題都是NP問題。)
NP-HARD:一個NP問題經由polynomial演算法轉化(reduce)之後所成的問題。
NP-COMPLETE:一個NP問題經由polynomial演算法轉化之後,仍為NP問題。
NP-HARD與NP-COMPLETE的不同:
NP-HARD不一定屬於NP問題,NP-HARD可以是NP問題,也可以是一個超越NP難度的問題,但若是NP-HARD的難度仍然是NP,則這個NP-HARD就是一個NP-COMPLETE。