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



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.

  • 1
    $\begingroup$ What does "unlikely" mean here? $\endgroup$ – Gerry Myerson Mar 7 '11 at 22:54
  • $\begingroup$ 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 :-) $\endgroup$ – Michal R. Przybylek Mar 8 '11 at 0:19

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

  • $\begingroup$ @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? $\endgroup$ – LowerBounds Mar 7 '11 at 21:01
  • 3
    $\begingroup$ (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. $\endgroup$ – Luca Trevisan Mar 10 '11 at 21:34
  • 1
    $\begingroup$ (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). $\endgroup$ – Luca Trevisan Mar 10 '11 at 21:39
  • 1
    $\begingroup$ 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 $\endgroup$ – Luca Trevisan Mar 10 '11 at 21:43
  • 1
    $\begingroup$ which can then be simulated in PSPACE, and hence in $P^C$, given a polynomial size advice string, and hence in $P^C/poly$ $\endgroup$ – Luca Trevisan Mar 10 '11 at 21:44

Your Answer

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

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