可以在多項式時間內求解的問題稱為易解的，而不能在多項式時間內求解的問題稱為難解的。

P類問題：多項式類型，是一類能夠用（確定性的）算法在多項式的時間內求解的判定問題。

只有判定問題才屬于P

不可判定問題：某些判定問題是不能用任何算法求解的，則稱這種判定問題為不可判定問題。否則就稱作可判定問題。

例如：Halting problem(停機問題)：給定一段計算機程序和他的一個輸入，判斷該程序對于該輸入是會中止還是會無限的運行。

證明停機問題是不可判定問題：反證法，通過構造一個輸出和解決停機問題的算法的輸出相反的程序使得自己陷入矛盾。

不確定算法：對于判定問題，猜測一個解，并且可以判斷這個解是否是正確的解的算法。

如果一個不確定算法在驗證階段的時間效率是多項式級的，我們說它是不確定多項式類型的。

NP類問題：可以用不確定多項式算法求解的判定問題。

大多數判定問題都是屬于NP類的。

• 所有的P類問題都是NP問題
• 停機問題是不屬于NP的判定問題

未解之謎：P類問題是NP問題的一個真子集還是P類問題其實就是NP問題

多項式化簡：可以使用一個多項式算法將一個判定問題的真實例轉化為另一個判定問題的真實例，假實例轉化為假實例。

NP完全（complete）問題：

• 屬于NP類型
• NP中的任何問題都能夠在多項式時間內化簡為該問題

例如：合取范式可滿足性問題就是一個NP完全問題。

NP完全性的定義意味著：即使我們僅僅得到了一個NP完全問題的多項式確定算法，也說明所有的NP問題都能夠用一個確定算法在多項式的時間內解出，即P=NP。

NP難（hard）問題：

• NP中的任何問題都能夠在多項式時間內化簡為該問題
• 不一定是NP問題，因此NPH比NPC的范圍廣