P-完全

在計算複雜度理論內，標示了P-完全的決定型問題對於分析

1. 哪些問題很難有效的平行處理，
2. 哪些問題很難在有限空間內解決掉。

相當的有用。

更正式的說，一個決定型問題是P-完全(一個P裡面的完全問題)：若這問題本身在P裡面，且所有在P內的問題，都可以化約為此問題。

特定的化約方式會產生使用差異而且會影響問題集合的大小。 若我們使用NC的化約，亦即，可以在多項式對數時間內，以平行運作的電腦在多項式個數之內的處理器下完成的化約，基於一個未被證明的假設 NC ≠ P，則我們可知所有的P-完全問題在NC之外，因此無法被有效率的平行處理化。如果我們使用比較弱的 log-space 化約，前面的說法維持為真，但是多了一個P-完全問題會在L之外的推論， 基於另一個較弱的，尚未被證明的假設L ≠ P。這裡需要注意到根據後者定義出的P-完全 會是一個比前者小一點的集合。

動機

找到一個有效率平行處理P-完全問題的方法會導出NC = P的結論(另一個雖沒有證明，但是一般認為是否的假說)。

另外，我們也可以將之視為"需要超過對數空間的問題"；因為，一個針對P-完全問題提出使用對數空間解決的演算法 (using the definition based on log-space reductions) 將會推導出L = P(另一個雖沒有證明，但是一般認為是否的假說)。

P-完全問題

最基本的P-完全問題是：給定一個圖靈機，此機器的輸入，以及一個數字T (以一進制表示)，這個給定的圖靈機是否會在 T 步驟之內結束運算？？這個問題是P-完全證明如下：

首先，這個問題包含於P之內，因為我們可以讓圖靈機實際模擬跑完前面T個步驟來得到結論。這只會耗費多項式的時間。

又，如果我們可以平行化這個問題，那就代表我們必須要允許一個圖靈機能平行處理任何問題。而若這個問題在NC之內，那所有包含在P的問題都將也可以化約為此問題，故得證。

若這個數字是以二進位系統表示，則這個問題會變成EXPTIME-完全.

這個問題展示了一個在研究P-完全問題的理論常用的技巧。我們並不關注在這問題是否可以快速的用平行機器處理，我們關注的地方在於這個問題是否在使用平行機器時會變的比起使用非平行的機器快速"很多"。因此，我們要先將問題改寫為P的版本。這就是為何我們需要將T以一進位表示。若數字T是使用二進位表示 (一個包含n個零與一的字串，n = log T)，那麼用最直觀的演算法運作的時間就會變成2ⁿ. 但是，若T是用一進位系統表示 (一個包含T個一的字串)，則花費的時間就變成只有n(因為跑的時間不變，但是輸入資料變大了，因此時間複雜度下降)。 藉著以一進位而非二進位來表示T， we have reduced the obvious sequential algorithm 從對數時間轉換到到線性時間。 因此將這個問題使用序列解法的時間限制在P之內。 Then, it will be in NC 若且唯若這問題是可以平行化處理的。

許多其他的問題也已被證明屬於P-完全，因此廣泛的被認為是自然屬於序列化(也就是，不容易平行化)的。 這些包含了以下的問題(無論是否是以決定型問題的方式表示，時間上都一樣為P-完全):

要證明一個給定的問題是P-完全，一個常見的作法是將一個已知是P-完全的問題化約為這個給定的問題。

在1999年，Jin-Yi Cai 和 D. Sivakumar，基於Ogihara的理論，推導出若存在一個稀疏語言屬於P-完全，則L = P。

未知是否為P-完全的問題

有一些問題尚不清楚是屬於NP-難或者是P。這一些問題(例如說，整數分解)被懷疑是比較困難的。 類似的有些問題尚不清楚是屬於P-完全或者NC，但是一般被認為是不容易平行化的。這類問題的範例有找出兩給定整數最大公因數的決定型問題版本，和給出對擴展歐幾里得算法出入兩個整數之後的答案。

参考文献

来源

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. 1995. Limits To Parallel computation; P-完全ness Theory. ISBN 0-19-508591-4. — Develops the theory, then catalogs 96 P-完全 problems.
• Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. A List of P-完全 Problems. Kyushu University, RIFIS-TR-CS-17. December 1990.