On pseudorandomness and resource-bounded measure (Q5941070): Difference between revisions

In this paper we extend a key result of \textit{N. Nisan} and \textit{A. Wigderson} [J. Comput. System Sci. 49, No. 2, 149-167 (1994; Zbl 0821.68057)] to the nondeterministic setting: for all \(\alpha >0\) we show that if there is a language in \(E=DTIME(2^{O(n)})\) that is hard to approximate by nondeterministic circuits of size \(2^{\alpha n}\), then there is a pseudorandom generator that can be used to derandomize \(BP\cdot NP\) (in symbols, \(BP\cdot NP=NP)\). By applying this extension we are able to answer some open questions in \textit{J. H. Lutz} [Theory Comput. Systems 30, No. 2, 429-442 (1997; Zbl 0872.68049)] regarding the derandomization of the classes \(BP\cdot \Sigma^{P}_{k}\) and \(BP\cdot \Theta^{P}_{k}\) under plausible measure theoretic assumptions. As a consequence, if \(\Theta^{P}_{2}\) does not have \(p\)-measure 0, then \(AM\cap coAM\) is low for \(\Theta^{P}_{2}\). Thus, in this case, the graph isomorphism problem is low for \(\Theta^{P}_{2}\). By using the Nisan--Wigderson design of a pseudorandom generator we unconditionally show the inclusion \(MA \subseteq ZPP^{NP}\) and that \(MA\cap coMA\) is low for \(ZPP^{NP}\).