簡介
在計算複雜度理論中， P是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。
P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如 RP與 BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n指令來解決的問題。很多情況下存在著更難的複雜度問題。
在P中令人注目的問題
P包含了很多已知的自然問題，例如決定性版本的線性規劃，計算最大公因數，以及發現最大吻合。在2002年，判別一個數是否為質數也被人解出是一個 P問題。與功能性問題（function problem）相關的類別是 FP。
與其他類別的關係
P的擴大集合是 NP，此複雜度類別是一個可在多項式時間以非確定型圖靈機決定答案的問題的集合。因此我們可知道 P是 NP的子集，且雖然未證明，但大部分專家相信P是NP的嚴格子集（即NP一定大於且包含P集合）。
P也已知至少大於 L一個可在對數量級的記憶體空間上決定的問題的類別。一個判定算法使用了O(log n)的空間就不可能使用超過2= n的時間，因為這是所有可能組合方式的總數，因此 L是 P的子集合。另一個重要問題是： L是否相等於 P？我們已知 P= AL（問題可在對數記憶體上以另類圖靈機（alternating Turing machine）解決的問題之集合），而 P也已知不大於 PSPACE（可在多項式空間判定的問題）。再一次，我們面對 P是否等於 PSPACE的未知問題。整理一下上述問題：
EXPTIME指的是可在指數時間解答的問題類別。在上列的類別關係中，只有兩個嚴格包含關係是確定的：
•L嚴格包含於PSPACE集合中。
在P問題中最困難的是P完備問題。
另一個 P的擴大集合是 P/poly，或 非統一多項式時間。若一個問題落於 P\poly，則它可以在依據輸入內容的長度下給予提示字串（advice string）的情況下，以確定性多項式時間解決。然而，不像 NP，此多項式時間機器不需要偵測偽造提示字串；因為它不是一個驗證機器。 P/poly是一個幾乎包含所有實際算法的巨大類別，包含所有 BPP。如果 P/poly包含了 NP，則整個多項式階層將會下降到第二階層。另一方面，它也包含一些不切實際的算法，包含一些可決定問題，例如一元版的任何非決定性問題。
性質
多項式時間算法擁有 組裝封閉性。換句話說，若我寫了一個內容是多項式時間的函式（若視函式呼叫為固定時間），且其它被本函式呼叫的副函式也屬於多項式時間，則整個組合起來的算法也會是多項式時間。因此 P是自我低陷的，這也是 P被認為是無關機器類型的主要理由：任何機器特徵（例如隨機存取）可以用多項式時間算法模仿的話，可在一些更簡單的機器以其他多項式時間算法組合併化約而成，且時間複雜度依然是P。
歷史
Kozen指出 Cobham 與 Edmonds 是 "最可信，最早創造 多項式時間這個名詞的人"。
