S_2^p subseteq ZPP^{NP}

摘要

We show that the class S p 2 is a subclass of ZPP 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 S p 2 becomes the strongest version to date of the Karp-Lipton Theorem.