Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
Ker‐I Ko · Journal of the ACM · 1990
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.