Abstract
Vikraman Arvind and Johannes Köbler
Abstract:
We extend a key result of Nisan and Wigderson to the nondeterministic
setting. By applying this extension we are able to answer some
questions left open by Lutz regarding the derandomization of the Sigma
and Theta classes of the polynomial hierarchy under plausible measure
theoretic assumptions. Further, by using the Nisan-Wigderson design of
a pseudorandom generator, we unconditionally show that MA is a
subclass of ZPP(NP) and that the intersection of MA and co-MA is low
for ZPP(NP).