圖檔來源于維基百科
左圖在假設P≠NP的情況下有效，右圖在假設P=NP的情況下有效
在假定P≠NP的情況下, 有
NP問題：可以在多項式時間内被驗證的問題。或者說，可以在非确定性多項式時間内被解決的問題。
即可以在非确定型圖靈機上在多項式時間内找出解的問題。NP問題可以在多項式時間内被驗證，但是不确定是否可以在多項式時間内找出解。
P問題：可以在多項式時間内被解決的問題。
即可以在确定性圖靈機上在多項式時間内找出解的問題。如果一個問題是P問題，那麼毫無疑問我們可以在多項式時間内驗證它。
NP-Hard問題：如果可以證明某問題有一個子問題是NP-Hard問題，那麼該問題是一個NP-Hard問題。
即已知一個NPC問題L'，如果我們可以把L'歸約為L,則L是NP-Hard。通俗的講，已經有一個很難的問題L',而L問題比L'更難解決，那麼該問題就是NP-Hard問題。NP-Hard問題不确定是否可以在多項式時間内被驗證。
NP-Complete問題：如果一個問題已經被證明是一個NP-Hard問題，并且可以證明該問題是一個NP問題，那麼該問題是NPC問題。
即已知一個NPC問題L'，如果我們可以把L'歸約為L，且L可以在多項式時間内被驗證，那麼L是一個NPC問題。
其中，P, NP, NP-Hard, NP-Complete是不同的複雜性類，用于将所有的算法問題進行分類，以确定目前算法的難度。
多項式時間可解的問題：如果對于某個确定的常數k,存在一個能在O(nk)時間内求解出某具體問題的算法，就說該具體問題是一個多項式時間可解問題。
多項式時間内可被驗證的問題：是一個判定問題，答案隻有是或否。例如，存在某具體問題，我們猜想該問題有一個可行解x，如果對于某個确定的常數k，存在一個能在O(nk)時間内驗證x是否是該具體問題可行解的算法，就說該具體問題是一個多項式時間可被驗證的問題。
一般來說，大家往往将多項式時間内可解的問題稱作易處理的問題，将超多項式時間内解決的問題稱作不易處理的問題。
NPC問題的鼻祖SAT問題：著名的
古克-李芬定理（由
Leonid Levin與Cook獨立證出
SAT問題是NPC問題，簡化過但依舊艱深的
證明在此）。
References:
維基百科：P/NP問題 維基百科：NP-Complete 維基百科：NP-hardness 維基百科：計算複雜性理論《算法導論》第3版 第34章
tips: 上下标的markdown文法
上标: <sup>上标内容</sup>
下标: <sub>下标内容</sub>