Symmetric alternation captures BPP
From MaRDI portal
Publication:1272661
DOI10.1007/s000370050007zbMath0912.68054OpenAlexW2043280328MaRDI QIDQ1272661
Alexander Russell, Ravi Sundaram
Publication date: 3 January 1999
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s000370050007
Related Items (18)
More on BPP and the polynomial-time hierarchy ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ The landscape of communication complexity classes ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Complexity limitations on one-turn quantum refereed games ⋮ Arthur and Merlin as oracles ⋮ The consequences of eliminating NP solutions ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ ON HIGHER ARTHUR-MERLIN CLASSES ⋮ 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 ⋮ Enumerations of the Kolmogorov function ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Reducing the number of solutions of NP functions
This page was built for publication: Symmetric alternation captures BPP
