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

In article <9bc56a5f-4986-4b80-bc91-58a4fa4f9f14@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
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?

What you can certainly do is fix a particular Turing machine M that calls
oracles in a fixed manner, and let the oracle A vary. For each choice of A,
M^A will accept some language. As you let A vary, you'll get a family of
languages. It would probably not make much sense to call such a family a
"complexity class" though.

As an example, sometimes people talk about "volume oracles" for polyhedra
in space. Instead of specifying a region in space by, say, a list of
explicit linear inequalities, I could hand you black box that will answer
any question of the form "Is the point P in the region?" with a yes or no
answer. An algorithm for computing the volume of such a region is a Turing
machine with a "slot" where you can stick in an arbitrary volume oracle as
part of the input. Some surprising results can be proved in this kind of
setting; in particular, there are randomized algorithms for estimating the
volume that are provably better than any deterministic algorithm. This is
an oracle-separation result of a slightly different kind from that of
Baker-Gill-Solovay.

You could also allow M to have some finite number of "oracle slots" so
that it can access several different oracles at a time. But since M is
finite, you can't have M access infinitely many oracles. You could try
to let both M and A vary simultaneously, but if you're not careful, the
result will be that *every* language will be accepted by some M^A.
--
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
.

Relevant Pages

  • Re: Interesting bug
    ... >which the C64 derived). ... >So structured BASIC existed on the C64 or similar machines. ... the possibility of implementing structured programming languages on such ... Merely the practicality of having such implementations in the ...
    (comp.lang.c)
  • Re: A 21st Century Apple II?
    ... It's certainly a benefit of resource constrained machines that quality ... when you consider total cost. ... It's also responsible for popularising many of the architectural ... since languages in popular use prior to that lacked ...
    (comp.sys.apple2)
  • Re: suggest a new Star Trek TV show
    ... affected certain key alloys and made certain kinds of machines used by ... From a transporter pad to another pad, ... The Universal Translator is really good at languages that have already ... The Starship Enterprise leaves Earth to discover what's happened to the ...
    (rec.arts.sf.tv)
  • Re: whats it worth to write a short program for polynomial multiplication?
    ... compile time, it is likely that the user will have to ... Most OO programming languages work that way. ... will also work on the POWER machines and related one. ...
    (sci.math.symbolic)
  • Re: Challenge for lisp lovers....
    ... representation of numbers a particular language implementation uses. ... I do care about other languages. ... Lisp Machines were almost tied to a single ...
    (comp.lang.lisp)