圖書館:User:Ttanxu/多項式譜系

Bluedeck Library 圖書館卡

Bluedeck Library 圖書館卡

本頁面為「User:Ttanxu/多項式譜系」的存檔，該頁面已遭刪除，本頁面僅供參考用。

存檔UTC時間	2018年8月12日 04:24
存檔編者	ThirdThink
當前版本號	50829136

取得正常維基源碼

{{d|O1}}

在 計算複雜性理論， 多項式譜系是一系列複雜度類，用以從 P, NP 和 co-NP 產生預言機。 它是數理邏輯里算數階層和分析階層的限定資源意義上的對應。

定義

有很多多項式譜系的等價定義。{{Ordered list}}

多項式譜系中的複雜度類的關係

可交換圖相當的時間多項式分層結構。 箭頭表示。

定義表明了如下的關係：

性質

未解決的計算機科學問題： ${\displaystyle }$ (更多的未解決計算機科學問題)

Each class in the polynomial hierarchy contains $\leq _{\rm {m}}^{\mathsf {P}}$-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is closed under $\leq _{\rm {m}}^{\mathsf {P}}$-reductions: meaning that for a class C in the hierarchy and a language $L\in {\mathcal {C}}$, if $A\leq _{\rm {m}}^{\mathsf {P}}L$, then $A\in {\mathcal {C}}$ as well. These two facts together imply that if $K_{i}$ is a complete problem for $\Sigma _{i}^{\mathsf {P}}$, then $\Sigma _{i+1}^{\mathsf {P}}={\mathsf {NP}}^{K_{i}}$, and $\Pi _{i+1}^{\mathsf {P}}={\mathsf {coNP}}^{K_{i}}$. For instance, $\Sigma _{2}^{\mathsf {P}}={\mathsf {NP}}^{\mathsf {SAT}}$. In other words, if a language is defined based on some oracle in C, then we can assume that it is defined based on a complete problem for C. Complete problems therefore act as "representatives" of the class for which they are complete. [[:Category:序位]] [[:Category:結構複雜度理論]]