NPC

"P"
為一組Problem的集合, 在此集合下的問題都有deterministic algorithm,其皆可在polynomial time下完成, 即 O(n^k).

"NP"
同上,but "deterministic" 換成 "non-deterministic"
(i,e 若對此問題給亦可能的解, 能在 O(n^k) 時間下去證明此解是否為正確)

"NP-hard"
一NP問題 is polynomial-time reducible to 另一個問題
(polynomial-time reducible是為了不改變問題的性質)

"NP-Complete"
存在一problem x
x 屬於  NP 且 x 屬於NP-hard
<=> x  屬於 NP-Complete
(i,e NPC中的問題在worst case下並沒有 O(n^k)的演算法可解)
(i,e worst case下需exponential time or even harder)

這幾類的目的, 是主要為了將problem依難度做分類.
(ha...有點導果為因= =...)

說實在的我最近也在研究有關NP-Comlete的相關issue, 但好抽象= =.....

refer from:
http://en.wikipedia.org/wiki/NP-complete
http://www.csie.ntnu.edu.tw/~u91029/noun.html
http://www.csie.ntnu.edu.tw/~u91029/NP.png