29
$\begingroup$

By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.

I think this is a proof: if $EXP\neq BPP$ then from [IW98] we get that BPP has such a simulation. Otherwise we have that $EXP=BPP$, which implies $RP=NP$ (because $NP \subseteq BPP$) and $EXP \in PH$. Now if $NP=RP=ZPP$ we have that $PH$ collapses to $ZPP$ and as a result $EXP$, but this cannot happen because of the assumption, so $RP\neq ZPP$ and this by the Kabanets paper "Easiness assumptions and hardness tests: trading time for zero error" implies that RP has such a simulation and as a result also NP.

This sounds like it could be a useful gap theorem. Does anyone know if it appears anywhere?

$\endgroup$
  • $\begingroup$ Very interesting. I haven't seen this argument before, but I'm not by any means an expert in these things... $\endgroup$ – arnab Aug 25 '10 at 11:03
  • 4
    $\begingroup$ (Just for reference): Identical question on MO: mathoverflow.net/questions/35945. Maybe someone finds the comments there inspiring. $\endgroup$ – M.S. Dousti Sep 30 '10 at 9:55
  • 2
    $\begingroup$ Why does NP in ZPP imply PH in ZPP? $\endgroup$ – Lance Fortnow Mar 10 '17 at 12:49
  • 4
    $\begingroup$ ZPP is closed under complement, and contained in NP. So, $\mathrm{NP\subseteq ZPP}$ implies NP = ZPP = coNP, hence PH = NP = ZPP. $\endgroup$ – Emil Jeřábek Mar 30 '17 at 11:51

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.