Article ID Journal Published Year Pages File Type
429921 Journal of Computer and System Sciences 2007 11 Pages PDF
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