ZPP is Hard Unless RP is Small
Philippe Moser · Maynooth University ePrints and eTheses Archive (Maynooth University) · 2002
We use Lutz's resource bounded measure theory to prove that, either RP is small, or ZPP is hard. More precisely, we prove that if RP has not p-measure zero, then EXP equals ZPP on infinitely many input lengths, i.e. there are infinitely many input lengths on which ZPP is hard. Second we prove that if NP has not p-measure zero, then derandomization of AM is possible on infinitely many input length, i.e. there are infinitely many input lengths such that NP = AM. 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 Ʃᴾᵢ algorithm can be simulated infinitely often by a subexponential co-nondeterministic time algorithm, having oracle access to Ʃᴾᵢ -2 , or BP Ʃᴾᵢ = Ʃᴾᵢ .