question on relativization of an algorithm

Hello,

I was reading Lance Fortnow's paper on relativization and I hit a bit
of a snag as far as my understanding goes.

"It is a misnomer to relativize a complexity class C. Instead,
suppose we take an enumeration of machines for C and give them some
access mechanism to an oracle set A. We then say the relativized
class C^A consists of the languages recognized by the acceptance
criteria for C applied to the machines using the oracle A."

What I don't understand is what exactly the "result" is when we
relativize an algorithm. If I have an algorithm, say one that decides
the language DIVISIBLEBYFOUR, and give it access to a SAT oracle, what
is the result? Is it a single machine? Is it a language associated
with a machine? Or is it several machines? I'm quite confused.

Any help anyone could provide would be appreciated.

-Phil

In article <84d03033-7501-477e-8f97-7eb33bb99b2d@x41g2000hsb.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>I was reading Lance Fortnow's paper on relativization and I hit a bit
>of a snag as far as my understanding goes.
>
>"It is a misnomer to relativize a complexity class C. Instead,
>suppose we take an enumeration of machines for C and give them some
>access mechanism to an oracle set A. We then say the relativized
>class C^A consists of the languages recognized by the acceptance
>criteria for C applied to the machines using the oracle A."
>
>What I don't understand is what exactly the "result" is when we
>relativize an algorithm. If I have an algorithm, say one that decides
>the language DIVISIBLEBYFOUR, and give it access to a SAT oracle, what
>is the result? Is it a single machine? Is it a language associated
>with a machine? Or is it several machines? I'm quite confused.

Fortnow doesn't use the term "relativize an algorithm" in your quotation,
and I doubt that he uses it elsewhere.

But more to the point, you shouldn't think of running through the
unrelativized machines one at a time and adding an oracle to each
one somehow. Instead, take the definition of a machine and modify
the definition so that access to the oracle is allowed. The class
of all machines satisfying the new definition is the class of oracle
machines that you want, and the class of languages accepted by some
oracle machine is the relativized complexity class.
--
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 Aug 22, 4:48 pm, tc...@lsa.umich.edu wrote:
> In article <84d03033-7501-477e-8f97-7eb33bb99...@x41g2000hsb.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >I was reading Lance Fortnow's paper on relativization and I hit a bit
> >of a snag as far as my understanding goes.
>
> >"It is a misnomer to relativize a complexity class C. Instead,
> >suppose we take an enumeration of machines for C and give them some
> >access mechanism to an oracle set A. We then say the relativized
> >class C^A consists of the languages recognized by the acceptance
> >criteria for C applied to the machines using the oracle A."
>
> >What I don't understand is what exactly the "result" is when we
> >relativize an algorithm. If I have an algorithm, say one that decides
> >the language DIVISIBLEBYFOUR, and give it access to a SAT oracle, what
> >is the result? Is it a single machine? Is it a language associated
> >with a machine? Or is it several machines? I'm quite confused.
>
> Fortnow doesn't use the term "relativize an algorithm" in your quotation,
> and I doubt that he uses it elsewhere.
>
> But more to the point, you shouldn't think of running through the
> unrelativized machines one at a time and adding an oracle to each
> one somehow. Instead, take the definition of a machine and modify
> the definition so that access to the oracle is allowed. The class
> of all machines satisfying the new definition is the class of oracle
> machines that you want, and the class of languages accepted by some
> oracle machine is the relativized complexity class.
> --
> 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


Hmm, ok. Thanks. I'm still confused about some things, but that does
answer my question.
-Phil

On Aug 22, 4:48 pm, tc...@lsa.umich.edu wrote:
> In article <84d03033-7501-477e-8f97-7eb33bb99...@x41g2000hsb.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >I was reading Lance Fortnow's paper on relativization and I hit a bit
> >of a snag as far as my understanding goes.
>
> >"It is a misnomer to relativize a complexity class C. Instead,
> >suppose we take an enumeration of machines for C and give them some
> >access mechanism to an oracle set A. We then say the relativized
> >class C^A consists of the languages recognized by the acceptance
> >criteria for C applied to the machines using the oracle A."
>
> >What I don't understand is what exactly the "result" is when we
> >relativize an algorithm. If I have an algorithm, say one that decides
> >the language DIVISIBLEBYFOUR, and give it access to a SAT oracle, what
> >is the result? Is it a single machine? Is it a language associated
> >with a machine? Or is it several machines? I'm quite confused.
>
> Fortnow doesn't use the term "relativize an algorithm" in your quotation,
> and I doubt that he uses it elsewhere.
>
> But more to the point, you shouldn't think of running through the
> unrelativized machines one at a time and adding an oracle to each
> one somehow. Instead, take the definition of a machine and modify
> the definition so that access to the oracle is allowed. The class
> of all machines satisfying the new definition is the class of oracle
> machines that you want, and the class of languages accepted by some
> oracle machine is the relativized complexity class.
> --
> 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 see your point. Thank you.
-Phil