We use Lutz's resource bounded measure theory to prove that, either \tbf{RP} is
small, or \tbf{ZPP} is hard.
More precisely, we prove that if \tbf{RP} has not p-measure zero, then
\tbf{ZPP} equals \tbf{EXP} on almost half the input lengths.
Second, we prove that that if \tbf{RP} has not p-measure zero, then for every $k \geq 1$,
\tbf{ZPP} is not included in $\mbf{DTIME}(2^{O(n^k)})$ for almost half the
input lengths $n$, i.e.
on almost half the input lengths
\tbf{ZPP} is hard.
Next, we prove that if \tbf{NP} has not p-measure zero, then derandomization of
\textbf{AM} is possible on almost half the input lengths, i.e.
$\mbf{NP} = \mbf{AM}$ on almost half the input lengths.
Finally, we prove easiness versus randomness tradeoffs for classes in the polynomial
time hierarchy.
We show that it appears to every strong adversary, that either,
every $\sig[i]$ algorithm can be simulated infinitely often by a subexponential
co-nondeterministic time algorithm, having oracle access to $\sig[i-2]$, or
$\sig[i] = \mbf{BP} \sig[i] $.

Keywords:Complexity, Randomness

We use Lutz's resource bounded measure theory to prove that either \tbf{RP} is
small or \tbf{ZPP} is hard. More precisely we prove that if \tbf{RP} has not p-measure zero, then \tbf{EXP} is contained
in $\mbf{ZPP}/n$.
We also show that if \tbf{RP} has not p-measure zero,
\tbf{EXP} equals \tbf{ZPP} on infinitely many input lengths, i.e. there
are infinitely many
input lengths on which \tbf{ZPP} is hard.
Finally, we prove that if \tbf{NP} has not p-measure zero, then derandomization of
\textbf{AM} is possible on infinitely many input length, i.e. there are
infinitely many input lengths
such that
$\mbf{NP} = \mbf{AM}$.