3
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Why does $EXP=BPP$ imply $RP=NP$? $\endgroup$ Commented Aug 18, 2010 at 16:40
  • $\begingroup$ I guess EXP = BPP implies BPP contains NP, which implies RP = NP. $\endgroup$ Commented Aug 19, 2010 at 5:27
  • $\begingroup$ Right, EXP=BPP implies $NP \subseteq BPP$ which implies $SAT \in RP$ , via search-to-decision reduction, thanks. $\endgroup$ Commented Aug 19, 2010 at 8:28

0

You must log in to answer this question.

Browse other questions tagged .