## Abstract

We show that if a complexity class C is closed downward under polynomial-time majority truth-table reductions (≤_{mtt}^{p}), then practically every other "polynomial" closure property it enjoys is inherited by the corresponding bounded two-sided error class BP[C]. For instance, the Arthur-Merlin game class AM [B1] enjoys practically every closure property of NP. Our main lemma shows that, for any relativizable class D which meets two fairly transparent technical conditions, we have C^{BP[C]} {Mathematical expression}BP[D^{C}]. Among our applications, we simplify the proof by Toda [Tol], [To2] that the polynomial hierarchy PH is contained in BP[⊕P]. We also show that relative to a random oracle R, PH^{R} is properly contained in ⊕P^{R}.

Original language | English (US) |
---|---|

Pages (from-to) | 229-243 |

Number of pages | 15 |

Journal | Mathematical Systems Theory |

Volume | 28 |

Issue number | 3 |

DOIs | |

State | Published - May 1995 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Mathematics
- Computational Theory and Mathematics