P

我們可以將所有計算問題分為兩類，一類可以透過演算法解決，另一類無法解決。雖然有些問題可以解決，但我們可能無法在合理的時間內解決它們。可以解決的問題分為 P 和 NP 類。還有其他分類，但我們將重點關注 P 和 NP。這些分類稱為複雜度類。一般來說，P 類包含可以在合理時間內解決的問題，而 NP 類包含那些無法解決的問題。

複雜度類 P

${\text{P}}=\bigcup _{k}{\text{TIME}}(n^{k})$

複雜度類 P 包含可以在有限時間內解決的問題。解決此類問題的演算法受輸入大小的多項式函式限制。複雜度分為兩部分，固定部分和可變部分。固定部分與其他任何東西無關，對於給定演算法來說是一個常數，但可變部分在同一問題的不同例項中會有所不同，例如，我們知道排序演算法對十個數進行排序所需的時間與對一百個數進行排序所需的時間不同。通常演算法所需的時間/空間將取決於問題的輸入大小。我們可以將演算法所需的時間/空間表示為常數和輸入大小的多項式函式之和。那些其解決演算法的複雜度可以用多項式表示的問題屬於 P 類。顯然，P 代表多項式。