11
$\begingroup$

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

$\endgroup$

1 Answer 1

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

$\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$ 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$ 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$ 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$ Mar 4, 2011 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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