# Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

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?

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