0
$\begingroup$

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!

$\endgroup$

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ What does "unlikely" mean here? $\endgroup$ Mar 7, 2011 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$ Mar 8, 2011 at 0:19
17
$\begingroup$

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

$\endgroup$
6
  • $\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$ Mar 7, 2011 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$ Mar 10, 2011 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$ Mar 10, 2011 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$ Mar 10, 2011 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$ Mar 10, 2011 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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