__
Revision #1 to TR02-015 | 8th April 2002 00:00
__
#### ZPP is hard unless RP is small Revision of: TR02-015

**Abstract:**
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

__
TR02-015 | 13th February 2002 00:00
__

#### ZPP is hard unless RP is small

**Abstract:**
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}$.