MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 8 down vote accepted

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...)

share|cite|improve this answer
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. – Sebastian Ben Daniel Aug 10 '10 at 23:14
More is known: if $EXP\subseteq P/\text{poly}$, then $EXP=PH=MA$, due to Babai, Fortnow, Nisan, and Wigderson. – Emil Jeřábek Mar 3 '11 at 12:25
@Emil, of course (in fact I used this in some recent papers)... but that doesn't strengthen the above arguments, does it? – Ryan Williams Mar 4 '11 at 3:21
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). – Emil Jeřábek Mar 4 '11 at 11:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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