Keep learning

• 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。

如果一個問題屬於 NP-hard，那麼所有屬於 NP 的問題都要能reduce 到這個問題上面，也就是說這個問題比所有 NP 的問題都要更難。
如果一個問題是 NP-complete，兩個條件:
(1) 此問題屬於 NP (2) 此問題為 NP-hard

也就是說NP 的問題裡面，有一部份是最難的，所有其他的 NP 問題都能 reduce 到這些問題上面這一群問題就稱為 NP-complete 的問題！所以 NP-hard 和 NP-complete 都是比所有 NP 問題都還要難的問題，差別在於 NP-complete 還是在 NP 之內，是 NP-hard 裡面屬於 NP 的問題！

資料來源：http://cey.cs.au.edu.tw/algo/down/NP.txt