\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

DOI10.1016/j.jcss.2003.07.015zbMath1133.68020OpenAlexW2331432079MaRDI QIDQ859979

Jin-Yi Cai

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

zbMATH Keywords

complexity theorycomplexity classesapproximate countingKarp-Lipton theoremsymmetric alternationirrefutable proofwitness sampling

Mathematics Subject Classification ID

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