# On power of $P/poly$

(1) We know that $EXP ⊄ P/poly ⇒ BPP$ is in $SUBEXP$. Does $SUBEXP ⊄ P/poly$ mean $P=BPP$ or anything close?

(2) We know that if $NP$ is in $P/poly$ then $PH$ collapses to second level. What is the consequence if $\oplus P$ is in $P/poly$?

• Polynomials grow more slowly than 2^n, so for sufficiently large n, there will be more possible length-n queries than the length of the advice. ​ For n that's not large enough, the NP machine can just have part of the language hard-coded. ​ For large-enough n, the advice can be the oracle's outputs for the n-bit encodings of the polynomially-many smallest nonnegative integers. ​ ​ ​ ​ – user12859 May 2 '16 at 19:36
• Does that make it clear? ​ In any case, the "good collapse" I mentioned, which follows from this paper, is that ​ coNP $\subseteq$ NP/poly ​ implies ​ PH collapses to S$_2\hspace{-0.02 in}$P$^{NP}$. ​ ​ ​ (Directly from the definitions, one gets ​ (S$_2\hspace{-0.02 in}$P)$^{NP}$ = S$_2\hspace{-0.05 in}\left(\hspace{-0.02 in}P^{\hspace{.02 in}NP}\hspace{-0.02 in}\right)$ , ​ so my previous sentence is unambiguous.) ​ ​ ​ ​ ​ ​ ​ ​ – user12859 May 2 '16 at 20:02
• Comments are not for extended discussion; this conversation has been moved to chat. – Gilles 'SO- stop being evil' May 2 '16 at 20:45
• Please use the chatroom Gilles created, rather than discussing the question in the comments here. Thank you. – D.W. May 4 '16 at 1:06
• @D.W why do you have to delete comment? – Bread Winner May 4 '16 at 1:46