P-完全 在計算複雜度理論內標示了P完全的決定型問題對於分析 哪些問題很難有效的平行處理 哪些問題很難在有限空間內解決掉 相當的有用 更正式的說一個決定型問題是P完全一個P裡面的完全問題若這問題本身在P裡面且所有在P內的問題都可以化約為此問題 特定的化約方式會產生使用差異而且會影響問題集合的大小 若我們使用NC的化約亦即可以在多項式對數時間內以平行運作的電腦在多項式個數之內的處理器下完成的化約基於一個未被證明的假設 NC  P則我們可知所有的P完全問題在NC之外因此無法被有效率的平行處理化如果我們使用比較弱的 logspace 化約前面的說法維持為真但是多了一個P完全問題會在L之外的推論 基於另一個較弱的尚未被證明的假設L  P這裡需要注意到根據後者定義出的P完全 會是一個比前者小一點的集合