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