期刊名称:Electronic Colloquium on Computational Complexity
印刷版ISSN:1433-8092
出版年度:2001
卷号:2001
出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要: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.