Welcome to MathOverflow

Question

0

1

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!

flag	asked Mar 7 2011 at 18:17 LowerBounds 473●2●12

Michal R. Przybylek · Accepted Answer · 2011-03-07 18:55:02Z UTC

7

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

Michal R. Przybylek
842●3●9

	What does "unlikely" mean here? – Gerry Myerson Mar 7 2011 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 2011 at 0:19

Luca Trevisan · Answer 2 · 2011-03-07 19:15:44Z UTC

8

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

answered Mar 7 2011 at 19:15

Luca Trevisan
183●7

	@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 2011 at 21:01
	@Luca: what is this oracle, and how does P/poly guess it in the advice string? – LowerBounds Mar 7 2011 at 21:02
	(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 2011 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 2011 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 2011 at 21:43

show 1 more comment

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.