S₂^P ZPP^NP

DOI10.1016/J.JCSS.2003.07.015zbMATH Open1133.68020OpenAlexW2331432079MaRDI QIDQ859979FDOQ859979

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

Recommendations

• Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
• Computing and Combinatorics
• New Collapse Consequences of NP Having Small Circuits
• On zero error algorithms having oracle access to one query
• New collapse consequences of NP having small circuits

zbMATH Keywords

complexity classescomplexity theoryapproximate countingKarp-Lipton theoremsymmetric alternationirrefutable proofwitness sampling

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• On Approximation Algorithms for # P
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• Relativized circuit complexity
• BPP and the polynomial hierarchy
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Uniform generation of NP-witnesses using an NP-oracle
• Simulating BPP using a general weak random source
• Oracles and queries that are sufficient for exact learning
• The Knowledge Complexity of Interactive Proof Systems
• Title not available (Why is that?)
• Turing machines that take advice
• Symmetric alternation captures BPP
• More on BPP and the polynomial-time hierarchy
• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
• New Collapse Consequences of NP Having Small Circuits
• If NP has polynomial-size circuits, then MA=AM
• On relativized exponential and probabilistic complexity classes
• Title not available (Why is that?)
• A note on sparse oracles for NP
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Title not available (Why is that?)

Cited In (17)

• The 1-versus-2 queries problem revisited
• The Complexity of Complexity
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Consequences of the provability of NP ⊆ P/poly
• Complexity limitations on one-turn quantum refereed games
• Complexity classes of equivalence problems revisited
• The landscape of communication complexity classes
• Robust simulations and significant separations
• Title not available (Why is that?)
• Approximate counting by hashing in bounded arithmetic
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
• Circuit lower bounds from learning-theoretic approaches
• Arthur and Merlin as oracles
• Hardness magnification near state-of-the-art lower bounds
• COMPLEXITY OF SHORT GENERATING FUNCTIONS
• The 1-Versus-2 Queries Problem Revisited

This page was built for publication: \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q859979)