ON CLOSURE-PROPERTIES OF BOUNDED 2-SIDED ERROR COMPLEXITY CLASSES

We show that if a complexity class C is closed downward under polynomi al-time majority truth-table reductions (less than or equal to(mtt)(p) ), then practically every other ''polynomial'' closure property it enj oys is inherited by the corresponding bounded two-sided error class BP [C]. For instance, the Arthur-Merlin game class AM [B1] enjoys practic ally every closure property of NP. Our main lemma shows that, for any relativizable class D which meets two fairly transparent technical con ditions, we have D-BP[C] subset of or equal to BP[D-C]. Among our appl ications, we simplify the proof by Toda [To1], [To2] that the polynomi al hierarchy PH is contained in BP[+P]. We also show that relative to a random oracle R,PHR is properly contained in +P-R.