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
.

Relevant Pages

  • Re: question on relativization of an algorithm
    ... criteria for C applied to the machines using the oracle A." ... Fortnow doesn't use the term "relativize an algorithm" in your quotation, ... and the class of languages accepted by some ...
    (comp.theory)
  • Re: question on relativization of an algorithm
    ... criteria for C applied to the machines using the oracle A." ... Fortnow doesn't use the term "relativize an algorithm" in your quotation, ... and the class of languages accepted by some ...
    (comp.theory)
  • Re: Paper - impossible to prove P=?NP
    ... deterministic Turing machine with an oracle for A in polynomial time; ... The difference from "real" Turing machines is that ... Then there exists a language A for which P^A = NP^A, ... So techniques for deciding P=?NP would have to be rather deeply ...
    (sci.crypt)
  • Re: Significance of "Relativizations of the P =? NP Question"
    ... oracle Y with respect to which P^Y!= NP^Y. ... "What happens when I try to relativize this proof? ... even though there is an oracle that separates the ... satisfactory general theory is lacking. ...
    (comp.theory)
  • Re: Significance of "Relativizations of the P =? NP Question"
    ... > oracle Y with respect to which P^Y!= NP^Y. ... "What happens when I try to relativize this proof? ... It is interesting that you say a general theory is lacking. ... I was once thinking about whether a diagonalization proof was possible, ...
    (comp.theory)