New Collapse Consequences of NP Having Small Circuits
New Collapse Consequences of NP Having Small Circuits
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.
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English