Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
Author:
Open Access
- 1 April 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 37 (2) , 415-438
Abstract
The probabilistic polynomial-time hierarchy (BPH) is the hierarchy generated by applying the BP-operator to the Meyer-Stockmeyer polynomial-time hierarchy (PH), where the BP-operator is the natural generalization of the probabilistic complexity class BPP. The similarity and difference between the two hierarchies BPH and PH is investigated. Oracles A and B are constructed such that both PH( A ) and PH( B ) are infinite while BPH( A ) is not equal to PH( A ) at any level and BPH( B ) is identical to PH( B ) at every level. Similar separating and collapsing results in the case that PH( A ) is finite having exactly k levels are also considered.Keywords
This publication has 20 references indexed in Scilit:
- Relativized Polynomial Time Hierarchies Having Exactly K LevelsSIAM Journal on Computing, 1989
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Are there interactive protocols for co-NP languages?Information Processing Letters, 1988
- Immunity and simplicity in relativizations of probabilistic complexity classesRAIRO - Theoretical Informatics and Applications, 1988
- Random oracles separate PSPACE from the polynomial-time hierarchyInformation Processing Letters, 1987
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- The polynomial-time hierarchy and sparse oraclesJournal of the ACM, 1986
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977