Re: question on relativization of an algorithm
- From: PhilipJWhite@xxxxxxxxx
- Date: Sat, 23 Aug 2008 17:46:30 -0700 (PDT)
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
Hmm, ok. Thanks. I'm still confused about some things, but that does
answer my question.
-Phil
.
- References:
- question on relativization of an algorithm
- From: cplxphil
- question on relativization of an algorithm
- Prev by Date: Re: Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.
- Next by Date: Re: question on relativization of an algorithm
- Previous by thread: question on relativization of an algorithm
- Next by thread: Re: question on relativization of an algorithm
- Index(es):
Relevant Pages
|
