PP is as Hard as the Polynomial-Time Hierarchy
PP is as Hard as the Polynomial-Time Hierarchy
复制标题
PP 与多项式时间层次结构一样困难
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Seinosuke Toda
中科院分区：
文献类型：
--
作者：
Seinosuke Toda
在本文中，将两个有趣的复杂性类，PP和$ \ oplus {\ text {p}} $与pH（多项式时间层次结构）进行了比较。结果表明，pH中的每个集合都是多项式时间的图丁可还原为PP中的集合，并且pH包含在$ {\ text {bp}} \ cdot \ oplus \ oplus {\ text {p}} $中。由于结果的结果，因此，$ {\ text {pp}} \ subseteq {\ text {ph}}} $（或$ \ oplus {\ oplus {\ text {p}} \ subseteq {\ subseteq {\ subseteq { ）意味着pH的崩溃。还显示了一个更强的结果：PP（pH）中的每组都是多项式时间的Turing，可还原为PP中的集合。
In this paper, two interesting complexity classes, PP and $ \oplus {\text{P}}$, are compared with PH, the polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turing reducible to a set in PP, and PH is included in ${\text{BP}} \cdot \oplus {\text{P}}$. As a consequence of the results, it follows that ${\text{PP}} \subseteq {\text{PH}}$ (or $\oplus {\text{P}} \subseteq {\text{PH}}$) implies a collapse of PH. A stronger result is also shown: every set in PP(PH) is polynomial-time Turing reducible to a set in PP.