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

On Jul 30, 9:38 pm, tc...@xxxxxxxxxxxxx wrote:
In article <9bc56a5f-4986-4b80-bc91-58a4fa4f9...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

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


That's fascinating. So essentially, I can require that an algorithm
query an oracle at a particular time while it is running? I can
specify, that during a certain part of a TM's functioning, that it is
required to query an oracle, and not waste the one cycle it has to do
something else?

If you're not tired of answering my questions, I have another idea.
Is it possible to require that an oracle take, say, 2 cycles, or 5
billion cycles, to activate it, instead of one cycle, as it works
conventionally? Think of the number of cycles that it takes to
activate the oracle as the "activation energy," and you could write
something like X^(A/5) to mean that X can query A if it spends five
cycles of computation calling it. X^(A/1) would be equivalent to X^A.

Where did you learn all this, anyway? I see from your signature that
you went to MIT, so that probably explains how you know so much. Is
there a book or paper or site that discusses oracles in depth, or that
is used in courses to explain this material?

Thanks once again.

-Phil
.

Relevant Pages

  • Re: obvious ("dumb") question about oracles and P vs. NP
    ... Is it possible to require that an oracle take, say, 2 cycles, or 5 ... a lot of top researchers teach courses ... polytime algorithm in this way? ...
    (comp.theory)
  • Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
    ... way of thinking is that I assume that an Oracle has to be a computable ... but there should be an algorithm that can recognize all ... in finite time doesn't mean that we can't prove that the machine exists. ... supposed to be an infinite sequence of steps that *A itself had to execute*. ...
    (comp.theory)
  • Re: chaining algorithms together
    ... As mentioned, we can quantify strength. ... An algorithm which requires an oracle is called an /oracle ... SE be a symmetric encryption algorithm. ...
    (sci.crypt)
  • Re: games and multiple quantifiers
    ... is to consider what are called "primitive recursive" predicates. ... If a problem is decidable by an oracle Turing machine, ... So it can be expressed both in sigma-0-2 and pi-0-2 ...
    (sci.math)
  • http://www.phenoelit.net/lablog/oracle.sl wrote
    ... CEO of Red Database Security GmbH and Oracle ... Oracle Database 11g for Linux with a new password hashing algorithm. ... dynamically by other executables shipped with Oracle 11g, ...
    (comp.databases.oracle.server)