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?

  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.