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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Very interesting. I haven't seen this argument before, but I'm not by any means an expert in these things... $\endgroup$
    – arnab
    Commented Aug 25, 2010 at 11:03
  • 4
    $\begingroup$ (Just for reference): Identical question on MO: mathoverflow.net/questions/35945. Maybe someone finds the comments there inspiring. $\endgroup$
    – Sadeq Dousti
    Commented Sep 30, 2010 at 9:55
  • 2
    $\begingroup$ Why does NP in ZPP imply PH in ZPP? $\endgroup$
    – Lance Fortnow
    Commented Mar 10, 2017 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
    Commented Mar 30, 2017 at 11:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.