In a World of P=BPP
Oded Goldreich
We show that proving results such as BPP = P essentially
necessitate the construction of suitable pseudorandom generators (i.e.,
generators that suffice for such derandomization results). In particular,
the main incarnation of this equivalence refers to the standard notion of
uniform derandomization and to the corresponding pseudorandom gen-
erators (i.e., the standard uniform notion of “canonical derandomizers”).
This equivalence bypasses the question of which hardness assumptions
are required for establishing such derandomization results, which has
received considerable attention in the last decade or so (starting with
Impagliazzo and Wigderson [JCSS, 2001]).
We also identify a natural class of search problems that can be solved by
deterministic polynomial-time reductions to BPP. This result is instru-
mental to the construction of the aforementioned pseudorandom genera-
tors (based on the assumption BPP = P), which is actually a reduction
of the “construction problem” to BPP