P (複雜度)

维基百科，自由的百科全书

在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。

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

[编辑] 在P中令人注目的問題

P包含了很多已知的自然問題，例如決定性版本的线性规划，計算最大公因數，以及發現最大吻合。在2002年，判別一個數是否為質數也被人解出是一個P問題^[1]。與功能性問題（function problem）相關的類別是FP。

[编辑] 與其他類別的關係

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

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

$\mbox{L} \subseteq \mbox{AL} = \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}$

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

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

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

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

[编辑] 性質

多項式時間演算法擁有組裝封閉性。換句話說，若我寫了一個內容是多項式時間的函數（若視函數呼叫為固定時間），且其它被本函數呼叫的副函數也屬於多項式時間，則整個兜起來的演算法也會是多項式時間。因此P是自我低陷的，這也是P被認為是無關機器類型的主要理由：任何機器特徵（例如隨機存取）可以用多項式時間演算法模仿的話，可在一些更簡單的機器以其他多項式時間演算法組合並化約而成，且時間複雜度依然是P。

[编辑] 歷史

Kozen^[3] 指出 Cobham 與 Edmonds 是 "最可信，最早創造多項式時間這個名詞的人"。

[编辑] 參考資料

↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
↑ Johnsonbaugh, Richard; Schaefer, Marcus, Algorithms, 2004 Pearson Education, page 458, ISBN 0-02-360692-4
↑ Kozen，Dexter C. (2006). Theory of Computation, 4，Springer. ISBN 1-84628-297-7.

C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.
Complexity Zoo: P, P/poly
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.1: Polynomial time, pp.971–979.
Michael Sipser (1997). Introduction to the Theory of Computation，PWS Publishing. ISBN 0-534-94728-X. Section 7.2: The Class P, pp.234–241.

一般的複雜度類 (more)
P • NP • 反NP • NP完全 • 反NP完全 • NP難 • UP • #P • #P-C • L • NL • NC • P完全 • PSPACE • PSPACE完全 • EXPTIME • EXPSPACE • PR • RE • 反RE • RE完全 • 反RE完全 • R • BQP • BPP • RP • ZPP • PCP • IP • PH

来自“http://zh.wikipedia.org../../../p/_/%28/P_%28%E8%A4%87%E9%9B%9C%E5%BA%A6%29.html”

页面分类: 複雜度類 | 最优化