S2 ZPPNP
Jin‐Yi Cai · 2001
We show that the class S2is a subclass of 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 S2becomes the strongest version to date of the Karp-Lipton Theorem. We also discuss the problem of finding irrefutable proofs for S2in ZPPNP.