PP is as Hard as the Polynomial-Time Hierarchy
Author:
- Seinosuke TodaSTSeinosuke Toda
- 1 October 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 20 (5) , 865-877
Abstract
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.
Keywords
This publication has 26 references indexed in Scilit:
- Probabilistic complexity classes and lownessJournal of Computer and System Sciences, 1989
- Relativizing complexity classes with sparse oraclesJournal of the ACM, 1986
- The polynomial-time hierarchy and sparse oraclesJournal of the ACM, 1986
- Some observations on the connection between counting and recursionTheoretical Computer Science, 1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- BPP and the polynomial hierarchyInformation Processing Letters, 1983
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Complete sets and the polynomial-time hierarchyTheoretical Computer Science, 1976
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976