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 generators

(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 instrumental to the

construction of the aforementioned pseudorandom generators

(based on the assumption BPP=P), which is actually a

reduction of the ``construction problem'' to BPP.

Caveat: Throughout the text, we abuse standard notation

by letting BPP, P etc denote classes of promise problems.

Some (non-minor but non-major) corrections and additions; most importantly see the last paragraph of the proof of Thm 4.9.

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 generators

(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 instrumental to the

construction of the aforementioned pseudorandom generators

(based on the assumption BPP=P), which is actually a

reduction of the ``construction problem'' to BPP.

Caveat: Throughout the text, we abuse standard notation

by letting BPP, P etc denote classes of promise problems.

correcting some typos, adding an observation re multiple samples (at the end of Sec 4.2).

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 generators

(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 instrumental to the

construction of the aforementioned pseudorandom generators

(based on the assumption BPP=P), which is actually a

reduction of the ``construction problem'' to BPP.

Caveat: Throughout the text, we abuse standard notation

by letting BPP, P etc denote classes of promise problems.