__
TR01-030 | 25th April 2001 00:00
__

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

**Abstract:**
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 to date of the Karp-Lipton Theorem.