11
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 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
    Commented Aug 10, 2010 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
    Commented Mar 3, 2011 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
    Commented Mar 4, 2011 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
    Commented Mar 4, 2011 at 11:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .