S₂^P ZPP^NP

DOI10.1016/J.JCSS.2003.07.015MaRDI QIDQ859979zbMATHOpenAlexFDO

Authors 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 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)

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

Cites work

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

Cited in

(17)

• Arthur and Merlin as oracles
• Complexity of short generating functions
• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• Hardness magnification near state-of-the-art lower bounds
• Hardness magnification near state-of-the-art lower bounds
• The landscape of communication complexity classes
• Circuit lower bounds from learning-theoretic approaches
• Complexity limitations on one-turn quantum refereed games
• Consequences of the provability of NP ⊆ P/poly
• Complexity classes of equivalence problems revisited
• Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
• The 1-versus-2 queries problem revisited
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• The 1-Versus-2 Queries Problem Revisited
• The Complexity of Complexity
• Approximate counting by hashing in bounded arithmetic

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)