On closure properties of bounded two-sided error complexity classes

K. W. Regan, J. S. Royer

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

We show that if a complexity class C is closed downward under polynomial-time majority truth-table reductions (≤mttp), 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 CBP[C] {Mathematical expression}BP[DC]. 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, PHR is properly contained in ⊕PR.

Original languageEnglish (US)
Pages (from-to)229-243
Number of pages15
JournalMathematical Systems Theory
Volume28
Issue number3
DOIs
StatePublished - May 1 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On closure properties of bounded two-sided error complexity classes'. Together they form a unique fingerprint.

  • Cite this