<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-03-10T12:49:49.943Z
Why does NP in ZPP imply PH in ZPP?
Lance Fortnow
CC BY-SA 3.0
2017-03-30T11:51:49.037Z
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
CC BY-SA 2.5
2010-08-25T11:03:34.383Z
Very interesting.  I haven't seen this argument before, but I'm not by any means an expert in these things...
arnab
CC BY-SA 2.5
2010-09-30T09:55:20.833Z
(Just for reference): Identical question on MO: http://mathoverflow.net/questions/35945/. Maybe someone finds the comments there inspiring.
Sadeq Dousti
<cc.complexity-theory><reference-request><complexity-classes><conditional-results>
Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?
Sebastian Ben Daniel
# Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

(Asked by: username_0 on 2010-08-23)

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?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, conditional-results

> **Comments:**
> **username_3**: Very interesting.  I haven't seen this argument before, but I'm not by any means an expert in these things...  
> **username_4**: (Just for reference): Identical question on MO: http://mathoverflow.net/questions/35945/. Maybe someone finds the comments there inspiring.  
> **username_1**: Why does NP in ZPP imply PH in ZPP?  
> **username_2**: ZPP is closed under complement, and contained in NP. So, $\mathrm{NP\subseteq ZPP}$ implies NP = ZPP = coNP, hence PH = NP = ZPP.  

---

## 0 answers

