Oracle, Relativization, and P vs NP, [Philosophical] - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T14:55:12Z http://mathoverflow.net/feeds/question/57965 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57965/oracle-relativization-and-p-vs-np-philosophical Oracle, Relativization, and P vs NP, [Philosophical] LowerBounds 2011-03-09T15:52:48Z 2012-04-01T04:54:35Z <p>I can understand why $P^A = NP^A$ does not imply $P=NP$, $A$ can "contain" the powers of NP.</p> <p>However, why does $P^B \neq NP^B$ not imply $P \neq NP$? It seems like if $P$ and $NP$ denote the same classes; then we should be able to arbitrarily substitute one for the other (as long as the only thing of interest is the computational model), and everything should stay the same.</p> <p>More generally, why is $A^X \neq B^X$ not a poof for $A \neq B$ ?</p> <p>I feel like there's a very fundamental piece of logic / reasoning I'm missing here.</p> <p>Thanks!</p> <p>EDIT: I understand the construction of the oracles A &amp; B. However, I still don't understand why the existence of $B$ not prove that $P \neq NP$.</p> http://mathoverflow.net/questions/57965/oracle-relativization-and-p-vs-np-philosophical/57967#57967 Answer by Emil Jeřábek for Oracle, Relativization, and P vs NP, [Philosophical] Emil Jeřábek 2011-03-09T16:10:11Z 2011-03-09T17:18:26Z <p>The notation is deceptive. $P^A$ is not something constructed from objects $P$ and $A$, but rather something <em>analogous</em> to $P$. In fact, $P$ is a special case of $P^A$, namely $P=P^\varnothing$. The same holds, mutatis mutandis, for $NP$. Removing the contrapositive for extra clarity, the proper way of stating your question is thus:</p> <p>Why $P^\varnothing=NP^\varnothing$ does not imply $P^A=NP^A$ for every $A$?</p> <p>Then it should be clear that there is no reason for this to hold, just like, say, $x^0=y^0$ does not imply $x^a=y^a$ for real $x,y,a$.</p> <p>EDIT: I'm not sure I should mention this, as it will probably just add to the confusion. However, under a proper notion of relativization, the implication $C_1^A\ne C_2^A\Rightarrow C_1\ne C_2$ does actually hold for “small classes” $C_1,C_2$, such as $AC^0[m]$, $TC^0$, $NC^1$, $L$, $NL$. See <a href="http://www.cs.toronto.edu/~sacook/homepage/rel-web.ps" rel="nofollow">this paper</a> by Aehlig, Cook, and Nguyen. The main reason which makes it work is that for all these classes, the depth of dependence of the oracle queries on each other is constant, hence any relativized function can be written as a finite composition of unrelativized functions and parallel oracle calls.</p> http://mathoverflow.net/questions/57965/oracle-relativization-and-p-vs-np-philosophical/57974#57974 Answer by Aubrey da Cunha for Oracle, Relativization, and P vs NP, [Philosophical] Aubrey da Cunha 2011-03-09T17:55:49Z 2011-03-09T17:55:49Z <p>I have wondered this before and the best answer I have heard is this: It is possible that while $P=NP$, $NP$ can get far more use out of an oracle than $P$ can. In essence, this is what happens in the construction of $B$ in your original question. We make use of the fact that an $NP$ algorithm can query exponentially many values of the oracle in only polynomial time, something that a $P$ algorithm could never do, even if $P=NP$.</p> http://mathoverflow.net/questions/57965/oracle-relativization-and-p-vs-np-philosophical/57979#57979 Answer by Holger for Oracle, Relativization, and P vs NP, [Philosophical] Holger 2011-03-09T18:27:10Z 2011-03-09T18:44:03Z <p>$P^A$ and $NP^A$ are shorthand notation to be used with care. What we mean by $\mathcal C^A$ depends heavily on the syntactical definition of the class $\mathcal C$ and is not well-defined if it's not clear which syntactical definition of $\mathcal C$ we are referring to. $\mathcal C^A$ is more an invariant of $\mathcal C$-machines than of the set of languages decided by $\mathcal C$-machines.</p> <p>While $P=NP$ means that $P$-machines can decide exactly the same languages as $NP$-machines, $P^B\neq NP^B$ for some oracle $B$ as proven by <a href="http://scholar.google.com/scholar?q=Baker+Gill+Solovay+Relativizations+of+the+P+NP+question" rel="nofollow">Baker, Gill, and Solovay (1975)</a> means that $P$-machines with additional access to the oracle $B$ can decide <em>strictly fewer</em> languages than $NP$-machines with access to $B$. Baker, Gill, and Solovay also give an oracle $A$ with respect to which these two types of machines can decide exactly the same languages.</p> http://mathoverflow.net/questions/57965/oracle-relativization-and-p-vs-np-philosophical/57988#57988 Answer by MassimoLauria for Oracle, Relativization, and P vs NP, [Philosophical] MassimoLauria 2011-03-09T19:53:25Z 2011-03-09T19:53:25Z <p>In the case you are interested, adding an oracle for a language $B$ to a machine means that such machine is able to do some non-trivial computation at cost of one atomic operation (ignoring the resources needed to prepare the query to the oracle). This make such machine more powerful (maybe not strictly ...). </p> <p>It is quite possible that a polynomial time <strong>non-deterministic</strong> machine $N$ can harness such power in ways that a mere <strong>deterministic</strong> machine $D$ cannot. That would mean that in presence of such oracle for $B$, the computational speed-up for $N$ is larger than the one for $D$.</p> http://mathoverflow.net/questions/57965/oracle-relativization-and-p-vs-np-philosophical/92793#92793 Answer by Marek Suchenek for Oracle, Relativization, and P vs NP, [Philosophical] Marek Suchenek 2012-04-01T04:44:52Z 2012-04-01T04:54:35Z <p>P = NP does not imply P^A = NP^A for every set A because for some A, NP^A allows more schemes of solutions than P^A does (via non-determinism). In particular, it is known for some A and B that P^A = NP^A and P^B not = NP^B.</p> <p>The reason for confusion here may result from the fact that the notation NP^A is misleading (or outright illogical); it would be less confusing if N(P^A) were used, instead.</p> <p>Then it would be more clear why P = NP does not necessarily imply P^A = N(P^A).</p> <p>Or, if one would like to really dot the "i", P(TM) should be used in lieu of P, P(NTM) in lieu of NP, P(TM^A) in lieu of P^A, and P(NTM^A) in lieu of NP^A, with PM meaning Turing machines and NTM - non-deterministic Turing machines, in obvious sense.</p> <p>Then it would become clear that any of the two axioms P(TM) = P(NTM) or P(TM) not = P(NTM) does not logically entail P(TM^A) = P(NTM^A) or P(TM^A) not = P(NTM^A) simply because the classes TM and NTM are not equal (despite the fact that they have the same "computational power") and, trivially, P(X) = P(Y) for some X, Y not equal to each other.</p> <p>The above is true under assertion that P, NP and similar (derivative) sets are fairly arbitrary (except, perhaps, P \subseteq NP, etc.). Otherwise, if P = NP is true then P non = NP (vacuously) proves everything, and so does P = NP if P non = NP is true. </p> <p>Marek Suchenek</p> <p><a href="http://csc.csudh.edu/suchenek/" rel="nofollow">http://csc.csudh.edu/suchenek/</a></p>