Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-015 | 8th April 2002 00:00

ZPP is hard unless RP is small Revision of: TR02-015

RSS-Feed




Revision #1
Authors: Philippe Moser
Accepted on: 8th April 2002 00:00
Downloads: 2859
Keywords: 


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


Paper:

TR02-015 | 13th February 2002 00:00

ZPP is hard unless RP is small





TR02-015
Authors: Philippe Moser
Publication: 27th February 2002 15:50
Downloads: 3183
Keywords: 


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}.



ISSN 1433-8092 | Imprint