More on BPP and the polynomial-time hierarchy

DOI10.1016/0020-0190(96)00016-6zbMath0875.68425OpenAlexW2079192595WikidataQ127179055 ScholiaQ127179055MaRDI QIDQ1351599

Ran Canetti

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00016-6

zbMATH Keywords

Computational complexityRandomnessTheory of computationInteractive proofs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (17)

The landscape of communication complexity classes ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Complexity limitations on one-turn quantum refereed games ⋮ Probabilism versus Alternation for Automata ⋮ Arthur and Merlin as oracles ⋮ The consequences of eliminating NP solutions ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ Proving SAT does not have small circuits with an application to the two queries problem ⋮ The 1-versus-2 queries problem revisited ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ On zero error algorithms having oracle access to one query ⋮ Complexity classes of equivalence problems revisited ⋮ Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) ⋮ Enumerations of the Kolmogorov function ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Reducing the number of solutions of NP functions

Cites Work

• Unnamed Item
• BPP and the polynomial hierarchy
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Symmetric alternation captures BPP
• The Knowledge Complexity of Interactive Proof Systems

This page was built for publication: More on BPP and the polynomial-time hierarchy