多項式時間（polynomial time）
多項式時間是定義 P 類的執行時間預算，感受它最容易的方式是靠對比。一個多項式時間演算法的步數受輸入大小的某個固定次方所界定，像 n、n^2 或 n^5；指數是事先釘死的常數，絕不允許隨 n 成長。相對地，指數時間演算法把輸入大小放到指數上，像 2^n，每多一個輸入符號就讓工作加倍。前者能擴展；後者不能。
形式上，若存在常數 k 使演算法對每個大小為 n 的輸入都在 O(n^k) 步內停機，則它在多項式時間內執行。例子：掃過清單一次是 O(n)，兩兩比較是 O(n^2)，用課本方法把兩個 n 乘 n 矩陣相乘是 O(n^3)，全都是多項式。判別的測試是：n 出現在底數（好：n^k）還是在指數（壞：k^n）。多項式的和、積或組合仍是多項式，這就是 P 對組合封閉的代數原因：一個多項式時間程式呼叫一個多項式時間子程式多項式次數，整體仍在多項式時間內執行。
多項式時間之所以擔綱主角，靠的是穩健性：Church-Turing 論題的多項式時間版本（Cobham-Edmonds 論題）指出，所有合理的確定型電腦彼此只以多項式減速互相模擬，所以「在多項式時間內執行」無論你是對圖靈機、筆電還是虛擬碼推理，意思都一樣。正是這種穩定性，讓我們能把多項式時間說成是問題的性質而非裝置的性質。只要把那個誠實的警告放在眼前：當指數或常數巨大時，原則上多項式並不等於實務上快速。
用小學方法把兩個 n 位數相乘是 O(n^2)，多項式。檢查 n 元素集合的全部 2^n 個子集以找出和為目標值的那一個是 O(2^n)，指數級。判斷的線索是 n 的位置：n^2 把 n 放在底數（多項式），而 2^n 把 n 放在指數（指數級）。
n 在底數（n^k）是多項式且可擴展；n 在指數（k^n）是指數級且不可。
多項式意指對「固定」常數 k 的 n^k；n^n 與 2^n 不是多項式。多項式對和、積、組合封閉，這就是 P 對組合封閉的原因；但指數或常數龐大的多項式仍然不切實際。