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

On Jul 30, 10:55 am, tc...@xxxxxxxxxxxxx wrote:
In article <126980d5-6bcf-4be7-9e47-7ac496906...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<cplxp...@xxxxxxxxx> 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



.