# “P vs NP” and “NP vs P/Poly”

It is known (1) P \subset P/poly (2) "NP \not\subset P/poly" --> "P \neq NP"

However, do we have a proof of: "P \neq NP" --> "NP \not\subset P/poly" ?

I.e. is there a world where P \neq NP, but NP \subset P/poly?

Thanks!

-

No, it is unknown whether $P \neq NP \Rightarrow NP \not\subset P/Poly$. However, one may show that if $NP \subset P/Poly$ then the polynomial hierarchy collapses on the second level, what is rather unlikely.

-
What does "unlikely" mean here? –  Gerry Myerson Mar 7 '11 at 22:54
Personal belief. OP asked if NP \subset P/Poly implies \Sigma_0^p = PH. The Karp–Lipton theorem states that if NP \subset P/Poly then \Sigma_2^p = PH. I would say that this statement is almost'' as good as the orginal one, and its conclusion is (almost) equally unbelievable :-) –  Michal R. Przybylek Mar 8 '11 at 0:19

There are oracles relative to which $P\neq NP$ but $NP\subseteq P/poly$.

-
@Luca: There exists oracles A, B s.t. P^A = NP^A ; P^B != NP^B shows that P vs NP can't be separated by relativizing proofs. The fact there exists C s.t. P^C != NP^C, but NP^C \subset P/poly^C ... what does this give us? –  LowerBounds Mar 7 '11 at 21:01
(Answering first question) The oracle C tells us that we cannot have a relativizing proof that derives the $NP\not\subseteq P/poly$ conclusion from the $P\neq NP$ assumption, so a theorem such as Karp-Lipton, which derives (via relativizing arguments) the $NP\not\subseteq P/poly$ conclusion from a stronger assumption, is about as much as we can hope to prove using relativizing arguments. –  Luca Trevisan Mar 10 '11 at 21:34
(Answering second question) I am not sure what was the original proof, but something like this work: fix a PSPACE-complete language L and pick a random function f:{0,1}^*->{0,1] such that, for each n, with probability 1/2 all values of f on {0,1}^n are 0, and with prob 1/2 there is exactly x in {0,1}^n, chosen randomly, such that f(x)=1; the random choices are independent for each f(). The oracle answers queries 0x by telling if x is in L, and queries 1x by giving the value of f(x). –  Luca Trevisan Mar 10 '11 at 21:39
Let C be the oracle. Consider the problem, given 1^n, of deciding if there is an $x$ in $\{ 0,1\}^n$ such that $f(x)=1$. This problem is always in $NP^C$, but with probability 1 over the choice of f it is not in $P^C$. For every choice of f, we have $NP^C \subseteq P/poly$, because if $L'$ can be decided by time-$p(n)$ nondeterministic machines with access to $C$, then given a description of $f$ for inputs of length up to $p(n)$ (which can be done with a polynomial number of bits) the whole computation is just a $NP$ computation with oracle access to PSPACE –  Luca Trevisan Mar 10 '11 at 21:43
which can then be simulated in PSPACE, and hence in $P^C$, given a polynomial size advice string, and hence in $P^C/poly$ –  Luca Trevisan Mar 10 '11 at 21:44