\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
type: Item
instance of: scholarly article
title: \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
zbMATH Open document ID: 1133.68020
published in: Journal of Computer and System Sciences
publication date: 2007-01-22T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 5117735
zbMATH Keywords: complexity theory
zbMATH Keywords: complexity classes
zbMATH Keywords: symmetric alternation
zbMATH Keywords: Karp-Lipton theorem
zbMATH Keywords: approximate counting
zbMATH Keywords: witness sampling
zbMATH Keywords: irrefutable proof
author: Jin-Yi Cai
MaRDI profile type: Publication
full work available at URL: j.jcss.2003.07.015
OpenAlex ID: W2331432079
cites work: Q4370034
cites work: Q4501553
cites work: New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: If NP has polynomial-size circuits, then MA=AM
cites work: Oracles and queries that are sufficient for exact learning
cites work: Uniform generation of NP-witnesses using an NP-oracle
cites work: More on BPP and the polynomial-time hierarchy
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: On relativized exponential and probabilistic complexity classes
cites work: Q3929039
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Turing machines that take advice
cites work: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
cites work: New Collapse Consequences of NP Having Small Circuits
cites work: BPP and the polynomial hierarchy
cites work: A note on sparse oracles for NP
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Symmetric alternation captures BPP
cites work: The polynomial-time hierarchy
cites work: On Approximation Algorithms for # P
cites work: Relativized circuit complexity
cites work: Simulating BPP using a general weak random source
DOI: 10.1016/J.JCSS.2003.07.015
description: scientific article; zbMATH DE number 5117735