\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
From MaRDI portal
Publication:859979
DOI10.1016/j.jcss.2003.07.015zbMath1133.68020OpenAlexW2331432079MaRDI QIDQ859979
Publication date: 22 January 2007
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2003.07.015
complexity theorycomplexity classesapproximate countingKarp-Lipton theoremsymmetric alternationirrefutable proofwitness sampling
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items
Circuit lower bounds from learning-theoretic approaches ⋮ The landscape of communication complexity classes ⋮ Robust simulations and significant separations ⋮ Complexity limitations on one-turn quantum refereed games ⋮ The Complexity of Complexity ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Arthur and Merlin as oracles ⋮ Unnamed Item ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ The 1-versus-2 queries problem revisited ⋮ Complexity classes of equivalence problems revisited ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Approximate counting by hashing in bounded arithmetic ⋮ COMPLEXITY OF SHORT GENERATING FUNCTIONS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- If NP has polynomial-size circuits, then MA=AM
- Turing machines that take advice
- BPP and the polynomial hierarchy
- Relativized circuit complexity
- Random generation of combinatorial structures from a uniform distribution
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- A note on sparse oracles for NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy
- Symmetric alternation captures BPP
- More on BPP and the polynomial-time hierarchy
- Uniform generation of NP-witnesses using an NP-oracle
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Simulating BPP using a general weak random source
- Oracles and queries that are sufficient for exact learning
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- On Approximation Algorithms for # P
- On relativized exponential and probabilistic complexity classes
- The Knowledge Complexity of Interactive Proof Systems
- New Collapse Consequences of NP Having Small Circuits
