S2p⊆ZPPNP

作者：

Highlights：

•

摘要

We show that the class S2p 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 S2p becomes the strongest version to date of the Karp–Lipton Theorem. We also discuss the problem of finding irrefutable proofs for S2p in ZPPNP.

论文关键词：Complexity Theory,Complexity classes,Symmetric alternation,Karp–Lipton Theorem,Approximate counting,Witness sampling,Irrefutable proof

论文评审过程：Received 17 October 2002, Revised 11 July 2003, Available online 14 November 2006.

论文官网地址：https://doi.org/10.1016/j.jcss.2003.07.015