ECCC-Report TR02-015https://eccc.weizmann.ac.il/report/2002/015Comments and Revisions published for TR02-015en-usMon, 08 Apr 2002 00:00:00 +0300
Revision 1
| ZPP is hard unless RP is small Revision of: TR02-015 |
Philippe Moser
https://eccc.weizmann.ac.il/report/2002/015#revision1 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
Mon, 08 Apr 2002 00:00:00 +0300https://eccc.weizmann.ac.il/report/2002/015#revision1
Paper TR02-015
| ZPP is hard unless RP is small |
Philippe Moser
https://eccc.weizmann.ac.il/report/2002/015We 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}$.
Wed, 27 Feb 2002 15:50:58 +0200https://eccc.weizmann.ac.il/report/2002/015