查看“︁P (複雜度)”︁的源代码

{{NoteTA
|G1 = IT
}}
[[File:Complexity subsets pspace.svg|thumb|复杂度关系韦恩图]]
在[[計算複雜度理論]]中，'''P'''（{{lang|en-us|polynomial time class}}）是在[[複雜度類別]]問題中可於[[圖靈機|確定型圖靈機]]以[[多項式]]量級（或稱[[多項式時間]]）求解的[[決定性問題]]。

'''P'''通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題，就算指數級非常高也可以算作「溫馴」，例如'''[[RP (複雜度)|RP]]'''與'''[[BPP (複雜度)|BPP]]'''問題。當然P類別存在很多現實處理上一點也[[P/NP问题#P真的容易处理吗？|不溫馴]]的問題，例如一些至少需要n<sup>1000000</sup>指令來解決的問題。很多情況下存在著[[P/NP问题#更难的问题|更難的複雜度問題]]

== 在P中令人注目的問題 ==
'''P'''包含了很多已知的自然問題，例如決定性版本的[[线性规划]]，計算[[最大公因數]]，以及發現[[maximum matching|最大匹配]]。在2002年，判別一個數是否為[[質數]]也被人解出是一個'''P'''問題<ref>Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "[http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PRIMES is in P] {{Wayback|url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |date=20171207171714 }}", ''Annals of Mathematics'' 160 (2004), no. 2, pp. 781–793.</ref>。與[[功能性問題]]相關的類別是[[FP (複雜度)|'''FP''']]。

== 與其他類別的關係 ==
'''P'''的擴大集合是[[NP (複雜度)|'''NP''']]，此複雜度類別是一個可在[[多項式時間]]以[[非確定型圖靈機]]決定答案的問題的集合。因此我們可知道'''P'''是'''NP'''的子集，且雖然[[P/NP問題|未證明]]，但大部分專家相信P是NP的嚴格子集（即NP一定大於且包含P集合）。<ref>Johnsonbaugh, Richard; Schaefer, Marcus, ''Algorithms'', 2004 Pearson Education, page 458, ISBN 978-0-02-360692-2</ref>

'''P'''也已知至少大於[[L (複雜度)|'''L''']]一個可在[[對數]]量級的[[記憶體空間]]上決定的問題的類別。一個判定演算法使用了O(log ''n'')的空間就不可能使用超過2<sup>O(log ''n'')</sup>=''n''<sup>O(1)</sup>的時間，因為這是所有可能組合方式的總數，因此'''L'''是'''P'''的子集合。另一個重要問題是：'''L'''是否相等於'''P'''？我們已知'''P'''='''AL'''（問題可在對數記憶體上以[[交替式图灵机]]解決的問題之集合），而'''P'''也已知不大於'''[[PSPACE]]'''（可在多項式空間判定的問題）。再一次，我們面對'''P'''是否等於'''PSPACE'''的未知問題。整理一下上述問題：

:<math>\mbox{L} \subseteq \mbox{AL} = \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}</math>

'''[[EXPTIME]]'''指的是可在指數時間解答的問題類別。在上列的類別關係中，只有兩個嚴格包含關係是確定的：
* '''P'''嚴格包含於'''EXPTIME'''之中。因此所有'''EXPTIME'''-hard問題在'''P'''集合之外，且最少一個'''P'''右方的包含關係是嚴格的（事實上，大部分人認為'''P'''右邊三個集合都是嚴格包含'''P'''）。
* '''L'''嚴格包含於'''PSPACE'''集合中。

在P問題中最困難的是[[P-完全]]問題。

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

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

== 歷史 ==
Kozen<ref>{{cite book | last = Kozen | first = Dexter C. | year = 2006 | title = Theory of Computation | url = https://archive.org/details/theorycomputatio00koze_939 | publisher = Springer | id = ISBN 978-1-84628-297-3 | pages = [https://archive.org/details/theorycomputatio00koze_939/page/n13 4]}}</ref>指出Cobham與Edmonds是最可信，最早創造'''多項式時間'''這個名詞的人。

== 註釋 ==
{{reflist}}

== 參考資料 ==
{{refbegin|2}}
* C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 978-0-201-53082-7.
* Complexity Zoo: [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#p P]，[https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#pslashpoly 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 978-0-262-03293-3. Section 34.1: Polynomial time, pp.971–979.
* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | id = ISBN 978-0-534-94728-6}} Section 7.2: The Class P, pp.234–241.
{{refend}}

{{复杂度类}}

[[Category:複雜度類]]
[[Category:數學最佳化]]