It is known
- $P \subset P/poly$
- $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!
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Mar 7, 2011 at 18:55
-
1$\begingroup$ What does "unlikely" mean here? $\endgroup$ Commented 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$ Commented Mar 8, 2011 at 0:19
$\begingroup$
$\endgroup$
6
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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Mar 10, 2011 at 21:44