(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$?

  • 1
    $\begingroup$ 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. ​ ​ ​ ​ $\endgroup$ – user12859 May 2 '16 at 19:36
  • $\begingroup$ 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.) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 May 2 '16 at 20:02
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Gilles 'SO- stop being evil' May 2 '16 at 20:45
  • 1
    $\begingroup$ Please use the chatroom Gilles created, rather than discussing the question in the comments here. Thank you. $\endgroup$ – D.W. May 4 '16 at 1:06
  • $\begingroup$ @D.W why do you have to delete comment? $\endgroup$ – Bread Winner May 4 '16 at 1:46

Your Answer

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

Browse other questions tagged or ask your own question.