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$ Aug 18, 2010 at 16:40
  • $\begingroup$ I guess EXP = BPP implies BPP contains NP, which implies RP = NP. $\endgroup$ 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$ Aug 19, 2010 at 8:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.