On the computational power of PP and (+)P
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 514-519
- https://doi.org/10.1109/sfcs.1989.63527
Abstract
Two complexity classes, PP and (+)P, are compared with PH (the polynomial-time hierarchy). The main results are as follows: (1) every set in PH is reducible in a certain sense to a set in PP, an (2) every set in PH is reducible to a set in (+)P under randomized polynomial-time reducibility with two-sided bounded error probability. It follows from these results that neither PP nor (+)P is a subset of or equivalent to PH unless PH collapses to a finite level. This is strong evidence that both classes are strictly harder than PH.Keywords
This publication has 13 references indexed in Scilit:
- On counting and approximationPublished by Springer Nature ,2005
- Turing machines with few accepting computations and low sets for PPJournal of Computer and System Sciences, 1992
- An oracle characterization of the counting hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- The polynomial-time hierarchy and sparse oraclesJournal of the ACM, 1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- On Approximation Algorithms for # PSIAM Journal on Computing, 1985
- On counting problems and the polynomial-time hierarchyTheoretical Computer Science, 1980
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- The polynomial-time hierarchyTheoretical Computer Science, 1976