Generalized lowness and highness and probabilistic complexity classes

We introduce generalized notions of low and high complexity classes and study their relation to structural questions concerning bounded probabilistic polynomial-time complexity classes. We show, for example, that for a bounded probabilistic polynomial-time complexity class =BP _k ^P ,L =H implies that the polynomial hierarchy collapses to . This extends Schöning's result for = _k ^P (L andH are the low and high sets defined by ). We also show, with one exception, that containment relations between the bounded probabilistic classes and the polynomial hierarchy are preserved by their low and high counterparts.LBPP andLBPNP are characterized asNP BPP andNP co-BPNP, respectively. These characterizations are then used to recover Boppana, Hastad, and Zachos's result that if co-NP BPNP, then the polynomial hierarchy collapses toBPNP, and Ko's result that ifNP BPP, then the polynomial hierarchy collapses toBPP.