On pseudorandomness and resource-bounded measure

V Arvind, J Köbler - Theoretical Computer Science, 2001 - Elsevier
Theoretical Computer Science, 2001Elsevier
In 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 (2 O (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 …
In 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 (2 O (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 · Σ P k and BP · Θ P k under plausible measure theoretic assumptions. As a consequence, if Θ P 2 does not have p-measure 0 , then AM ∩ coAM is low for Θ P 2. Thus, in this case, the graph isomorphism problem is low for Θ P 2. By using the Nisan–Wigderson design of a pseudorandom generator we unconditionally show the inclusion MA ⊆ ZPP NP and that MA ∩ coMA is low for ZPP NP .
Elsevier