Note that it would suffice to prove $EXP subseteq P/poly$ implies $NP = BPP$ (since the latter implies $NP = RP$).
I am pretty sure this is not known. $NP neq RP$ does not seem to imply any circuit lower bounds for $EXP$.
Note that $EXP subseteq P/poly$ does imply $P neq NP$. If $EXP subseteq P/poly$ then there is some fixed $k$ for which $TIME[2^n]$ has $n^k$-size circuits. Therefore $P subseteq TIME[2^n]$ has $n^k$-size circuits. But $P = NP$ implies that $Sigma_2 P = P$, and we know by Kannan's theorem that $Sigma_2 P$ does not have $n^k$-size circuits for any fixed $k$ -- this is a contradiction. (This result is due to Meyer, cited in the famous Karp-Lipton paper.)
I would suspect that one can prove $EXP subseteq P/poly$ implies $RP neq NP$ or maybe $ZPP neq NP$, but the above proof doesn't do the job. (Technically, since I believe $EXP notsubseteq P/poly$, the negation should imply everything...)
No comments:
Post a Comment