User:Bluedecklibrary/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:結構複雜度理論]]