P (複雜度) | 合法醫療器材資訊網

在計算複雜度理論中，P（polynomialtimeclass）是在複雜度類別問題中可於確定型圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。P通常表示那類 ...

維基百科，自由的百科全書

在計算複雜度理論中，P（polynomial time class）是在複雜度類別問題中可於確定型圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。

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

P包含了很多已知的自然問題，例如決定性版本的線性規劃，計算最大公因數，以及發現最大匹配。在2002年，判別一個數是否為質數也被人解出是一個P問題[1]。與功能性問題相關的類別是FP。

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

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