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

It is known

1. $$P \subset P/poly$$
2. $$NP \not\subset P/poly \Rightarrow P \neq NP$$

However, do we have a proof of: $$P \neq NP \Rightarrow 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.
• 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$.
• (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
• 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