P 類（class P）
/ pee /
想像整理一疊鈔票、在字典裡查一個字，或在地圖上找最短路線。當輸入變大，工作量也跟著變大，但很溫和——資料加倍，工作頂多變四倍，而不是百萬倍。P 就是所有「能以這種溫和成長方式解決」的決定問題（是非問題）所組成的俱樂部：存在一個演算法，總是給出正確的是非答案，而其執行時間被某個輸入規模的多項式所界定，像 n、n^2 或 n^3。
精確地說，一個決定問題屬於 P，若存在常數 c 與 k 以及一個演算法，使得對每個規模為 n 的輸入，它都在 c * n^k 步內停機並給出正確答案（在像隨機存取機器這樣的合理模型中、合理的二進位編碼下）。關鍵詞是「某個」多項式——n^2 與 n^100 都被允許，這個類別並不在意是哪一個。為什麼界線畫在多項式，而不是畫在 n^3？因為多項式正是那種「輸入放大時仍可掌控」、且「在合成下封閉」的執行時間：若你呼叫一個多項式時間的副程式多項式多次，整體仍是多項式。正是這種穩健性，使「多項式時間」成為「可有效解決」的標準數學替身。
P 是第一門課裡幾乎每個演算法的家：排序（O(n log n)）、最短路徑（Dijkstra）、最大流、匹配、質數判定（AKS 測試）。兩個誠實的提醒。第一，「多項式」是一個粗糙的漸進理想：n^100 的演算法屬於 P，實務上卻沒用；而 2^(0.0001 n) 的演算法雖不屬於 P，在真實輸入上卻可能贏過它——P 刻畫的是成長趨勢，不是在每個規模都保證快。第二，P 是針對決定問題定義的；像「找最短旅程」這種最佳化問題，是透過它的決定孿生（「存在長度至多 B 的旅程嗎？」）來處理的，而兩者通常可在多項式時間內互相轉換。
「這張公路地圖上兩座城市相連嗎？」屬於 P：從一座城市跑廣度優先搜尋；若抵達另一座，答「是」。在有 n 個節點、m 條邊的圖上，這花 O(n + m) 步——對輸入規模而言是舒服的多項式。無論地圖怎麼變大，時間都只線性成長。
P＝存在保證正確、且執行時間為 c * n^k（k 為某固定常數）的演算法的問題。
P 講的是決定性機器上的「最壞情況」多項式時間。「多項式」不等於「快」——n^100 也算數——「不屬於 P」也不等於「實務上慢」；這個類別是一條乾淨的理論界線，不是效能基準。