I guess the answer is that this unknown. Maybe this implies some "lowness" result on NP relative to BPP?


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 \not\subseteq P/poly$, the negation should imply everything...)

  • 2
    $\begingroup$ Thanks! Regarding $EXP \subseteq P/poly$ imply $P\neq NP$, from the assumption it follows that $EXP=\sigma_2$(Karp-Lipton due to Meyer) and $P=NP$ collapse PH to P, which imply that $P=EXP$, contradiction (Hartmanis and Stern using diagnolization). I think it's maybe simpler. Proving what you suggest could be interesting, I think $BPP\neq EXP$ is a consequence. $\endgroup$ – Sebastian Ben Daniel Aug 10 '10 at 23:14
  • $\begingroup$ More is known: if $EXP\subseteq P/\text{poly}$, then $EXP=PH=MA$, due to Babai, Fortnow, Nisan, and Wigderson. $\endgroup$ – Emil Jeřábek Mar 3 '11 at 12:25
  • $\begingroup$ @Emil, of course (in fact I used this in some recent papers)... but that doesn't strengthen the above arguments, does it? $\endgroup$ – Ryan Williams Mar 4 '11 at 3:21
  • $\begingroup$ No, it doesn't, but I thought it was relevant. Your post starts by contemplating whether $EXP\subseteq P/\mathrm{poly}$ implies the collapse of PH to BPP; we don't known how to do that, but we can at least collapse the hierarchy to the somewhat bigger class MA (though that's admittedly not a big deal, already $NP\subseteq P/\mathrm{poly}$ collapses the hierarchy to $S^P_2$ by the Karp–Lipton argument). $\endgroup$ – Emil Jeřábek Mar 4 '11 at 11:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.