P 類（class P）
如果你必須在整張計算地圖上畫一條線，把「這件事我們真的做得到」和「做不到」分開，複雜度理論家會把它畫在 P。P 是所有「確定型機器能在多項式時間內解出」的決定問題的類別。它是日常用語「高效」的形式化家園，而幾乎每個你會稱為實用的演算法——從排序到最短路徑到搜尋引擎——都住在它裡面。
精確地說，若存在一台確定型圖靈機與一個常數 k，使該機器能判定語言 L（總是停機並給出正確的是／否），且對每個大小為 n 的輸入都在 O(n^k) 時間內執行，則 L 屬於 P。等價地，P 是對所有固定 k 取 TIME(n^k) 的聯集。關鍵特徵是：指數 k 是一個不隨輸入成長的固定常數；n^2、n^3、n^100 全都是多項式，但 2^n 不是。P 有兩個性質使它成為正確的概念。它是穩健的：每個合理的確定型計算模型（多帶機、RAM 機、普通程式語言）彼此只以多項式額外開銷互相模擬，所以是否屬於 P 不取決於你挑哪一個。而它對組合封閉：把一個 P 演算法的多項式時間輸出餵給另一個，仍留在 P 裡，這讓我們能用小的高效程序組出大的。
兩則誠實的註記為 P 定錨。第一，P 是對決定問題（以語言表述的是／否問題）定義的；搜尋或最佳化任務要透過它的決定版本來研究。第二，P 是「可行」的理想化，而非它的完美同義詞。一個 n^100 時間、或藏著 10^40 常數的演算法，技術上屬於 P 卻毫無用處，而最壞情況多項式時間可能藏著好或壞的典型行為。所以把 P 當作可解的標準、行為良好的替身，理解它而非崇拜它。
可達性問題（給定一張圖與兩個頂點 s、t，是否存在從 s 到 t 的路徑？）屬於 P：廣度優先搜尋在 O(n + m) 時間內回答它，對圖的大小是多項式。質數判定（N 是質數嗎？）也屬於 P，由 AKS 演算法證明。相對地，SAT 沒有已知的多項式時間演算法，所以 SAT 不知道是否屬於 P。
可達性、排序、最短路徑與質數判定屬於 P；SAT 則不知是否屬於 P。
P 是對確定型機器上的決定問題定義的，且指數 k 必須是固定常數；2^n 不是多項式。P 是「高效」與模型無關的標準替身，但 n^100 演算法仍屬於 P、仍毫無用處。