Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 simulation. otherwise we have that $EXP=BPP$ which implies $RP=NP$ and $EXP \in PH$ now if $NP=RP=ZPP$ we have that $PH$ collapse to $ZPP$ and as a result $EXP$, but this cannot happen because of the assumption, so $RP\neq ZPP$ and this by Kabanets paper "easiness assumptions and hardness tests: trading time for zero error" implies that RP has such simulation and as a result also NP.

This sound like a basic result, anyone knows if it appears anywhere?

share|improve this question
Why does $EXP=BPP$ imply $RP=NP$? –  Ryan Williams Aug 18 '10 at 16:40
I guess EXP = BPP implies BPP contains NP, which implies RP = NP. –  Robin Kothari Aug 19 '10 at 5:27
Right, EXP=BPP implies $NP \subseteq BPP$ which implies $SAT \in RP$ , via search-to-decision reduction, thanks. –  Sebastian Ben Daniel Aug 19 '10 at 8:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.