New Collapse Consequences of NP Having Small Circuits
Johannes Köbler, Osamu Watanabe · SIAM Journal on Computing · 1998
We show that if a self-reducible set has polynomial-size circuits, then it is low for the probabilistic class ZPP (NP). As a consequence we get a deeper collapse of the polynomial-time hierarchy PH to ZPP(NP) under the assumption that NP has polynomial-size circuits. This improves on the well-known result in Karp and Lipton [ Proceedings of the 12th ACM Symposium on Theory of Computing, ACM Press, New York, 1980, pp. 302--309] stating a collapse of PH to its second level $\Sigmap_2$ under the same assumption. Furthermore, we derive new collapse consequences under the assumption that complexity classes like UP, FewP, and C=P have polynomial-size circuits. Finally, we investigate the circuit-size complexity of several language classes. In particular, we show that for every fixed polynomial s, there is a set in ZPP(NP) which does not have O(s(n))-size circuits.