MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.