Re: question on relativization of an algorithm

On Aug 22, 4:48 pm, tc...@xxxxxxxxxxxxx wrote:
In article <84d03033-7501-477e-8f97-7eb33bb99...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

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

Relevant Pages

  • Re: Oracle 9iR2 32bit on windows 2003 server 64bit
    ... Oracle won't use the extra memory in the machine. ... If Oracle does not support the configuration what is the ... the application's vendor is stating the Oracle version requirement. ... They had billing machines, but no LAN. ...
    (comp.databases.oracle.server)
  • Re: Cant connect error
    ... full "Programmer" install of Oracle. ... Although we have JDE available through terminal server, ... Oracle Client on the ... >> their machines. ...
    (microsoft.public.data.odbc)
  • Re: Access awake after 7 years?
    ... > who have DOS based machines. ... > But then what if they have only Commodore 64's? ... > db for the Commodore 64 called Oracle (no Really, ... running Windows 3.1 or DOS 6.0. ...
    (comp.databases.ms-access)
  • Re: Increasing Size of SGA_MAX in Oracle 10G
    ... machines at any given point of time. ... or any work arounds to this, thought to seek some advice before i ... This parameter defines the maximum size of the Oracle ... the same on the second instance or do we simply just restart instance ...
    (comp.databases.oracle.server)
  • question on relativization of an algorithm
    ... "It is a misnomer to relativize a complexity class C. ... criteria for C applied to the machines using the oracle A." ... Is it a language associated ...
    (comp.theory)