Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > S_2 ZPP:
Reports tagged with S_2 ZPP:
TR01-030 | 25th April 2001
Jin-Yi Cai

#### S_2^p \subseteq ZPP^{NP}

We show that the class ${\rm S}_2^p$ is a subclass of
${{\rm ZPP}^{\rm NP}}$. The proof uses universal hashing, approximate counting
and witness sampling. As a consequence, a collapse first noticed by
Samik Sengupta that the assumption NP has small circuits collapses
PH to ${\rm S}_2^p$
becomes the strongest version ... more >>>

ISSN 1433-8092 | Imprint