Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429921 | Journal of Computer and System Sciences | 2007 | 11 Pages |
Abstract
We show that the class is contained in ZPPNP. 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 becomes the strongest version to date of the Karp–Lipton Theorem. We also discuss the problem of finding irrefutable proofs for in ZPPNP.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics