[科普中國]-P復雜度

P嚴格包含于EXPTIME之中。因此所有EXPTIME-hard問題在P集合之外，且最少一個P右方的包含關系是嚴格的（事實上，大部分人認為P右邊三個集合都是嚴格包含P）。

簡介在計算復雜度理論中，P是在復雜度類問題中可于決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。

P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數(shù)級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現(xiàn)實處理上一點也不溫馴的問題，例如一些至少需要n指令來解決的問題。很多情況下存在著更難的復雜度問題。1

在P中令人注目的問題P包含了很多已知的自然問題，例如決定性版本的線性規(guī)劃，計算最大公因數(shù)，以及發(fā)現(xiàn)最大吻合。在2002年，判別一個數(shù)是否為質(zhì)數(shù)也被人解出是一個P問題。與功能性問題（function problem）相關的類別是FP。1

與其他類別的關系P的擴大集合是NP，此復雜度類別是一個可在多項式時間以非確定型圖靈機決定答案的問題的集合。因此我們可知道P是NP的子集，且雖然未證明，但大部分專家相信P是NP的嚴格子集（即NP一定大于且包含P集合）。

P也已知至少大于L一個可在對數(shù)量級的內(nèi)存空間上決定的問題的類別。一個判定算法使用了O(logn)的空間就不可能使用超過2=n的時間，因為這是所有可能組合方式的總數(shù)，因此L是P的子集合。另一個重要問題是：L是否相等于P？我們已知P=AL（問題可在對數(shù)內(nèi)存上以另類圖靈機（alternating Turing machine）解決的問題之集合），而P也已知不大于PSPACE（可在多項式空間判定的問題）。再一次，我們面對P是否等于PSPACE的未知問題。整理一下上述問題：

EXPTIME指的是可在指數(shù)時間解答的問題類別。在上列的類別關系中，只有兩個嚴格包含關系是確定的：

L嚴格包含于PSPACE集合中。

在P問題中最困難的是P完備問題。

另一個P的擴大集合是P/poly，或非統(tǒng)一多項式時間。若一個問題落于P\poly，則它可以在依據(jù)輸入內(nèi)容的長度下給予提示字串（advice string）的情況下，以確定性多項式時間解決。然而，不像NP，此多項式時間機器不需要偵測偽造提示字串；因為它不是一個驗證機器。P/poly是一個幾乎包含所有實際算法的巨大類別，包含所有BPP。如果P/poly包含了NP，則整個多項式階層將會下降到第二階層。另一方面，它也包含一些不切實際的算法，包含一些可決定問題，例如一元版的任何非決定性問題。1

性質(zhì)多項式時間算法擁有組裝封閉性。換句話說，若我寫了一個內(nèi)容是多項式時間的函數(shù)（若視函數(shù)呼叫為固定時間），且其它被本函數(shù)呼叫的副函數(shù)也屬于多項式時間，則整個組合起來的算法也會是多項式時間。因此P是自我低陷的，這也是P被認為是無關機器類型的主要理由：任何機器特征（例如隨機存?。┛梢杂枚囗検綍r間算法模仿的話，可在一些更簡單的機器以其他多項式時間算法組合并化約而成，且時間復雜度依然是P。1

歷史Kozen指出 Cobham 與 Edmonds 是 "最可信，最早創(chuàng)造多項式時間這個名詞的人"。1

本詞條內(nèi)容貢獻者為:

李宗秀 - 副教授 - 黑龍江財經(jīng)學院