Timeline for "P vs NP" and "NP vs P/Poly"
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 10, 2011 at 21:44 | comment | added | Luca Trevisan | which can then be simulated in PSPACE, and hence in $P^C$, given a polynomial size advice string, and hence in $P^C/poly$ | |
| Mar 10, 2011 at 21:43 | comment | added | Luca Trevisan | 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 | |
| Mar 10, 2011 at 21:39 | comment | added | Luca Trevisan | (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). | |
| Mar 10, 2011 at 21:34 | comment | added | Luca Trevisan | (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. | |
| Mar 7, 2011 at 21:02 | comment | added | LowerBounds | @Luca: what is this oracle, and how does P/poly guess it in the advice string? | |
| Mar 7, 2011 at 21:01 | comment | added | LowerBounds | @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? | |
| Mar 7, 2011 at 19:15 | history | answered | Luca Trevisan | CC BY-SA 2.5 |