Symmetric alternation captures BPP

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

zbMATH Keywords

complexity classessymmetric alternationsymmetric quantifiers

Mathematics Subject Classification ID

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

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