On pseudorandomness and resource-bounded measure

AbstractIn this paper we extend a key result of Nisan and Wigderson (J. Comput. System Sci. 49 (1994) 149–167) to the nondeterministic setting: for all α>0 we show that if there is a language in E=DTIME(2O(n)) that is hard to approximate by nondeterministic circuits of size 2αn, then there is a pseudorandom generator that can be used to derandomize BP·NP (in symbols, BP·NP=NP). By applying this extension we are able to answer some open questions in Lutz (Theory Comput. Systems 30 (1997) 429–442) regarding the derandomization of the classes BP·ΣPk and BP·ΘPk under plausible measure theoretic assumptions. As a consequence, if ΘP2 does not have p-measure 0, then AM∩coAM is low for ΘP2. Thus, in this case, the graph isomorphism problem is low for ΘP2. By using the Nisan–Wigderson design of a pseudorandom generator we unconditionally show the inclusion MA⊆ZPPNP and that MA∩coMA is low for ZPPNP