Abstract
Johannes Köbler and Osamu Watanabe
Abstract:
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 of Karp, Lipton, and
Sipser (1980) stating a collapse of PH to its second level under the
same assumption. As a further consequence, 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.