obvious ("dumb") question about oracles and P vs. NP

This is going to sound idiotic, but this has been troubling me.

From the Baker-Gill-Solovay proof, we find that there is an oracle A
s.t. NP^A = P^A, and an oracle B s.t. NP^B != P^B.

Here is my rather dumb question: Why is it that the second inequality
doesn't prove that P != NP? If there exists one oracle relative to
which NP and P are not equal, shouldn't that imply, in a certain
sense, that there is some "difference" between NP and P? Relative to
the oracle B, NP and P are provably different. Why doesn't that
translate to a proof that P != NP?

I know that this is basically just my own lack of understanding of
oracle machines, but that doesn't bring me any closer to understanding
this.

Thanks,
Phil

In article <c235cdee-7963-4dd2-884f-71e51ffd9535@k30g2000hse.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>From the Baker-Gill-Solovay proof, we find that there is an oracle A
>s.t. NP^A = P^A, and an oracle B s.t. NP^B != P^B.
>
>Here is my rather dumb question: Why is it that the second inequality
>doesn't prove that P != NP?

This is one of my pet peeves about the standard notation for oracles.

The notation "P^B" makes it look like you're starting with the object P and
then doing something to it. If that were the case, then your argument would
be correct. For if P = NP, then if you apply some operation to P, the
result should be the same as if you apply that same operation to NP, since
after all P and NP are (by assumption) the same thing.

However, that's not what "P^B" means. "P^B" is not obtained by starting
with the language P and then performing some operation on the language.
Instead, you're performing an operation on the *model of computation*.
Thus P^B is just something that is *analogous* to P---nothing more.

Here's an analogy that may help. Two companies A and B make the same amount
of money. Each company then hires an extra person. It doesn't follow that
A and B's profits will change by the same amount. Since A and B are
structured differently, the impact of hiring an extra person may differ.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

Ok, so what you are saying is that P and NP become not equal when the
model of computation is changed, because of how P and NP are defined?
How is this analogy: It would be like taking the words "mouse" and
"rodent" and saying that the letter "o" now means "q" (changing the
model of computation), and thus because "mquse" is not the same as a
"rqdent," a mouse and rodent are not the same thing. (Pretend that
mouse and rodent are equivalent; I was going to use cat and feline but
they don't share any letters.)

Is that about right? Also, do you think it might make sense to
reverse the notation? E.g., say "B^P != B^NP," because what you've
really done is allowed an oracle machine to enter the model of
computation, and then examined the complexity classes under the new
model.

Here's one final question. Would it be possible to prove P != NP if
someone could find somehow prove that X^A != X^B, where X is some
complexity class, and A and B are two oracles that would be equivalent
(somehow) if P = NP? In other words, does X^A != X^B imply A != B?

Thanks for the help, I think I'm getting a better understanding of the
subject.

-Phil

In article <45250138-976c-4c77-9a41-a55759f05709@m44g2000hsc.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>Ok, so what you are saying is that P and NP become not equal when the
>model of computation is changed, because of how P and NP are defined?

Right. I'm not sure about your mouse/rodent analogy, though.

Maybe a better analogy is this. I have two different machines A and B,
and they appear to produce identical widgets, but by very different
mechanisms. Now I go in to both machines and change every gear of type X
to a gear of type Y. The effect of this is unpredictable. In particular,
it doesn't follow that the modified machines will continue to produce the
same widgets. There may be a lot more gears of type X in machine A, for
example, and they might serve very different functions in the two machines.

>Is that about right? Also, do you think it might make sense to
>reverse the notation? E.g., say "B^P != B^NP," because what you've
>really done is allowed an oracle machine to enter the model of
>computation, and then examined the complexity classes under the new
>model.

If what you mean to say is that P^A is not necessarily equal to P^B
if A and B are different oracles, then certainly this is true.

>Here's one final question. Would it be possible to prove P != NP if
>someone could find somehow prove that X^A != X^B, where X is some
>complexity class, and A and B are two oracles that would be equivalent
>(somehow) if P = NP? In other words, does X^A != X^B imply A != B?

Yes, this is correct.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

On Jul 27, 1:56 pm, tc...@lsa.umich.edu wrote:
> In article <45250138-976c-4c77-9a41-a55759f05...@m44g2000hsc.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >Ok, so what you are saying is that P and NP become not equal when the
> >model of computation is changed, because of how P and NP are defined?
>
> Right. I'm not sure about your mouse/rodent analogy, though.
>
> Maybe a better analogy is this. I have two different machines A and B,
> and they appear to produce identical widgets, but by very different
> mechanisms. Now I go in to both machines and change every gear of type X
> to a gear of type Y. The effect of this is unpredictable. In particular,
> it doesn't follow that the modified machines will continue to produce the
> same widgets. There may be a lot more gears of type X in machine A, for
> example, and they might serve very different functions in the two machines.
>
> >Is that about right? Also, do you think it might make sense to
> >reverse the notation? E.g., say "B^P != B^NP," because what you've
> >really done is allowed an oracle machine to enter the model of
> >computation, and then examined the complexity classes under the new
> >model.
>
> If what you mean to say is that P^A is not necessarily equal to P^B
> if A and B are different oracles, then certainly this is true.
>
> >Here's one final question. Would it be possible to prove P != NP if
> >someone could find somehow prove that X^A != X^B, where X is some
> >complexity class, and A and B are two oracles that would be equivalent
> >(somehow) if P = NP? In other words, does X^A != X^B imply A != B?
>
> Yes, this is correct.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences


OK, I like your widget analogy pretty well.


> >Here's one final question. Would it be possible to prove P != NP if
> >someone could find somehow prove that X^A != X^B, where X is some
> >complexity class, and A and B are two oracles that would be equivalent
> >(somehow) if P = NP? In other words, does X^A != X^B imply A != B?
>
> Yes, this is correct.


Ok, interesting. Thanks again for all the help.

-Phil

Wait, one more thing.

If it's possible to say that X^A != X^B --> A != B, why doesn't
someone do this to prove P != NP....

Consider some complexity class X, maybe P. Let Q be the oracle from
Baker-Gill-Solovay's proof s.t. P^Q != NP^Q. Then let A equal the
union of every oracle for every language in P, unioned with Q, and let
B be the union of every oracle for every language in NP, also unioned
with Q. The effect is...

A = (U (oracle for x) x is an element of P) U oracle for Q
B = (U (oracle for x) y is an element of NP) U oracle for Q.

Then consider X^A and X^B. Then since the complexity class X has
access to an oracle for all languages in P plus an oracle for Q, X^A
should be something comparable to the language from Baker-Gill-
Solovay, except probably with a few extra languages thrown in, since
the Q oracle could be applied at any time. The other language should
be different from this one.

That's obviously far from a real proof...but I guess what I'm asking
is, is there some reason why that approach couldn't work?

-Phil

In article <126980d5-6bcf-4be7-9e47-7ac496906d8b@d45g2000hsc.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>Consider some complexity class X, maybe P. Let Q be the oracle from
>Baker-Gill-Solovay's proof s.t. P^Q != NP^Q. Then let A equal the
>union of every oracle for every language in P, unioned with Q, and let
>B be the union of every oracle for every language in NP, also unioned
>with Q. The effect is...
>
>A = (U (oracle for x) x is an element of P) U oracle for Q
>B = (U (oracle for x) y is an element of NP) U oracle for Q.

I'm not sure what you mean by taking the union of two oracles. Oracles are
normally defined by specifying a language (the oracle tells you whether a
given string is or is not in the language). By the union of two oracles,
do you mean the oracle obtained by taking the union of the languages in
question? But every string is in *some* polytime language, so taking the
union of all languages in P gives you the set of all strings. Or are you
trying to create a machine that has access to a bunch of different oracles
rather than just one oracle?
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

On Jul 30, 10:55 am, tc...@lsa.umich.edu wrote:
> In article <126980d5-6bcf-4be7-9e47-7ac496906...@d45g2000hsc.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >Consider some complexity class X, maybe P. Let Q be the oracle from
> >Baker-Gill-Solovay's proof s.t. P^Q != NP^Q. Then let A equal the
> >union of every oracle for every language in P, unioned with Q, and let
> >B be the union of every oracle for every language in NP, also unioned
> >with Q. The effect is...
>
> >A = (U (oracle for x) x is an element of P) U oracle for Q
> >B = (U (oracle for x) y is an element of NP) U oracle for Q.
>
> I'm not sure what you mean by taking the union of two oracles. Oracles are
> normally defined by specifying a language (the oracle tells you whether a
> given string is or is not in the language). By the union of two oracles,
> do you mean the oracle obtained by taking the union of the languages in
> question? But every string is in *some* polytime language, so taking the
> union of all languages in P gives you the set of all strings. Or are you
> trying to create a machine that has access to a bunch of different oracles
> rather than just one oracle?
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences


Yes, what I meant was giving a complexity class access to a number of
different oracles.

Is it possible to create a sort of "custom class" that has nothing to
do with complexity and give it access to oracles? Do the same
properties apply? I would think that they would. What I'm thinking
of is something like this: the class of all languages that are
decided by an algorithm that behaves in a precise manner: it makes
two queries to its oracles (or does something else that takes two
cycles), and then does a precise action after that.

So in other words, could I do this:

X = the class of all languages that are decided by machines that
behave in the precise manner X

And then say...

X^(A and B and C and D...)

where A, B, C, D, are oracles machines, and X has access to all of
them?

-Phil

In article <9bc56a5f-4986-4b80-bc91-58a4fa4f9f14@f36g2000hsa.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>So in other words, could I do this:
>
>X = the class of all languages that are decided by machines that
>behave in the precise manner X
>
>And then say...
>
>X^(A and B and C and D...)
>
>where A, B, C, D, are oracles machines, and X has access to all of them?

What you can certainly do is fix a particular Turing machine M that calls
oracles in a fixed manner, and let the oracle A vary. For each choice of A,
M^A will accept some language. As you let A vary, you'll get a family of
languages. It would probably not make much sense to call such a family a
"complexity class" though.

As an example, sometimes people talk about "volume oracles" for polyhedra
in space. Instead of specifying a region in space by, say, a list of
explicit linear inequalities, I could hand you black box that will answer
any question of the form "Is the point P in the region?" with a yes or no
answer. An algorithm for computing the volume of such a region is a Turing
machine with a "slot" where you can stick in an arbitrary volume oracle as
part of the input. Some surprising results can be proved in this kind of
setting; in particular, there are randomized algorithms for estimating the
volume that are provably better than any deterministic algorithm. This is
an oracle-separation result of a slightly different kind from that of
Baker-Gill-Solovay.

You could also allow M to have some finite number of "oracle slots" so
that it can access several different oracles at a time. But since M is
finite, you can't have M access infinitely many oracles. You could try
to let both M and A vary simultaneously, but if you're not careful, the
result will be that *every* language will be accepted by some M^A.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

On Jul 30, 9:38 pm, tc...@lsa.umich.edu wrote:
> In article <9bc56a5f-4986-4b80-bc91-58a4fa4f9...@f36g2000hsa.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >So in other words, could I do this:
>
> >X = the class of all languages that are decided by machines that
> >behave in the precise manner X
>
> >And then say...
>
> >X^(A and B and C and D...)
>
> >where A, B, C, D, are oracles machines, and X has access to all of them?
>
> What you can certainly do is fix a particular Turing machine M that calls
> oracles in a fixed manner, and let the oracle A vary. For each choice of A,
> M^A will accept some language. As you let A vary, you'll get a family of
> languages. It would probably not make much sense to call such a family a
> "complexity class" though.
>
> As an example, sometimes people talk about "volume oracles" for polyhedra
> in space. Instead of specifying a region in space by, say, a list of
> explicit linear inequalities, I could hand you black box that will answer
> any question of the form "Is the point P in the region?" with a yes or no
> answer. An algorithm for computing the volume of such a region is a Turing
> machine with a "slot" where you can stick in an arbitrary volume oracle as
> part of the input. Some surprising results can be proved in this kind of
> setting; in particular, there are randomized algorithms for estimating the
> volume that are provably better than any deterministic algorithm. This is
> an oracle-separation result of a slightly different kind from that of
> Baker-Gill-Solovay.
>
> You could also allow M to have some finite number of "oracle slots" so
> that it can access several different oracles at a time. But since M is
> finite, you can't have M access infinitely many oracles. You could try
> to let both M and A vary simultaneously, but if you're not careful, the
> result will be that *every* language will be accepted by some M^A.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences


That's fascinating. So essentially, I can require that an algorithm
query an oracle at a particular time while it is running? I can
specify, that during a certain part of a TM's functioning, that it is
required to query an oracle, and not waste the one cycle it has to do
something else?

If you're not tired of answering my questions, I have another idea.
Is it possible to require that an oracle take, say, 2 cycles, or 5
billion cycles, to activate it, instead of one cycle, as it works
conventionally? Think of the number of cycles that it takes to
activate the oracle as the "activation energy," and you could write
something like X^(A/5) to mean that X can query A if it spends five
cycles of computation calling it. X^(A/1) would be equivalent to X^A.

Where did you learn all this, anyway? I see from your signature that
you went to MIT, so that probably explains how you know so much. Is
there a book or paper or site that discusses oracles in depth, or that
is used in courses to explain this material?

Thanks once again.

-Phil