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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.