Thursday, 26 December 2013

computational complexity - Does $EXPneq ZPP$ implies sub-exponential simulation of BPP or NP?

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 $EXPneq 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 $RPneq 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?

No comments:

Post a Comment