P (polynomial time) 是由存在多項式複雜度解演算法的問題形成的集合。是一群Decision Problem的集合，這些問題皆可利用 確定性有解的演算法(Deterministic
Algorithm) 於Worst Case的情況下，在Polynomial Time Polynomial Time的複雜度內被解決

NP (nondeterministic polynomial time) 是由存在多項式複雜度驗證演算法的問題形成的集合。所謂 “NP” 是指Non-deterministic 與Polynomial兩個單字的簡寫
這類的問題只要給個解答，可以在Polynomial Time的複雜度內很快地驗證 (Verify) (Verify) 出這個解答是否正確。

此演算法包含兩步驟：

• Guessing，猜測 (此步驟屬於Nondeterministic)
• Verification，驗證（此步驟屬於deterministic）

• 由於決定性演算法為非決定性演算法的一個特例，且容易找到答案也會容易驗証答案。因此，P可視為NP的一個特例
• P⊂NP (O)
•  P=NP (?)

NP-hard:
此類問題至今仍未找到一個多項式複雜度的決定性演算法，且一般相信沒有多項式複雜度的決定性演算法存在。

NP-complete:

可以把所有 NP 問題歸約成具 NP 性質的 NPC 問題，這些問題雖然還沒有找到簡單的解法，但已經有找到簡單的驗證方法，也就是 NPC 問題是 NP問題與 NP-hard 問題的交集