5
$\begingroup$

I can understand why $P^A = NP^A$ does not imply $P=NP$, $A$ can "contain" the powers of NP.

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.

More generally, why is $A^X \neq B^X$ not a poof for $A \neq B$ ?

I feel like there's a very fundamental piece of logic / reasoning I'm missing here.

Thanks!

EDIT: I understand the construction of the oracles A & B. However, I still don't understand why the existence of $B$ not prove that $P \neq NP$.

$\endgroup$
3
  • 2
    $\begingroup$ An analogy is given at terrytao.wordpress.com/2009/08/01/… $\endgroup$ Mar 9, 2011 at 15:59
  • 2
    $\begingroup$ There is probably no function $f$ such that $f(A,X)=A^X$. $\endgroup$ Mar 9, 2011 at 16:07
  • 2
    $\begingroup$ What's philosophical about the question? It appears to me as a technical question with a very definite answer. $\endgroup$ Mar 9, 2011 at 19:38

5 Answers 5

13
$\begingroup$

The notation is deceptive. $P^A$ is not something constructed from objects $P$ and $A$, but rather something analogous 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:

Why $P^\varnothing=NP^\varnothing$ does not imply $P^A=NP^A$ for every $A$?

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$.

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 this paper 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.

$\endgroup$
4
$\begingroup$

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 ...).

It is quite possible that a polynomial time non-deterministic machine $N$ can harness such power in ways that a mere deterministic 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$.

$\endgroup$
3
$\begingroup$

$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.

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 Baker, Gill, and Solovay (1975) means that $P$-machines with additional access to the oracle $B$ can decide strictly fewer 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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

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.

Then it would be more clear why P = NP does not necessarily imply P^A = N(P^A).

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.

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.

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.

Marek Suchenek

http://csc.csudh.edu/suchenek/

$\endgroup$

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.